【3.3】指针、二分、SSM项目

二分查找

class Solution {public int search(int[] nums, int target) {int n = nums.length;int left = 0;int right = n - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] < target){left = mid + 1;}else if(nums[mid] > target){right = mid - 1;}else{return mid;}}return -1;}
}

模板说明：

int left = 0;
int right = n - 1;

说明是[left , right]的查找。

while(left <= right){

当退出while循环时，left = right + 1，比如[3,2]区间，此时区间中没有元素，说明查找了全部元素。

 left = mid + 1;
right = mid - 1;

因为是闭区间的查找，每次查找都查了mid元素，所以不用重复查找。如果不这样设置，当查找区间内不存在的数字时，会造成死循环（left = right = mid）。

• 27. 移除元素 - 力扣（LeetCode）

  快慢指针。

  class Solution {public int removeElement(int[] nums, int val) {int right = 0;int n = nums.length;for(int i = 0 ; i < n ; i ++){if(nums[i] == val){continue;}else {nums[right ++] = nums[i];}}return right;}
  }
  

• 977. 有序数组的平方 - 力扣（LeetCode）

  左右指针。

  class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length;int i = 0;int j = n - 1;int [] result =new int [n]; int k = n - 1;while(k >= 0){if(nums[i] * nums[i] >= nums[j] * nums[j]){result[k --] = nums[i] * nums[i];i ++;}else{result[k --] = nums[j] * nums[j];j --;}}return result;}
  }