二分法

首先数组中想使用二分法的前提是数组有序，如果有重复元素就得用到双指针来辅助

二分法其实就是利用中间值mid不断地修正左右指针left和right，让两端不断接近目标值，如果while的条件是（right >= left），也就是说左指针超过右指针，最后跳出条件后，右指针right是最接近目标值target的值

注意：
1.当在数组中查找x的平方根的整数时，就要考虑int的上下限问题，最好转为long操作，还有用除号时要注意right=x/2 + 1，不+1，就会在初始左右指针时直接相等 left=right

基础Java的二分法

1. 力扣：二分查找
   链接：https://leetcode-cn.com/problems/binary-search

    public int binarySearch(int[] nums, int target) {    //这句代码放在线面第二题中就会报数组越界，目前不知道为啥 if (nums[0] > target  || nums[nums.length-1] < target){     return -1; }int left = 0; int right = nums.length-1;//这要注意区间，如果两端都是闭区间，可以用等于 while (right >= left){     int mid = left + (right - left)/2;     if (target > nums[mid]){  left = mid+1;     }else if (target < nums[mid]){  right = mid -1;     }else {  return mid;     } } return -1;    }

带有重复值的有数数组，查找目标值的下标区间

2. 力扣：在排序数组中查找元素的第一个和最后一个位置
   链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

 public int[] searchRange(int[] nums, int target) { //通过二分法先找到第一个目标值,然后滑动 int index = binarySearch(nums, target); if (index == -1){     return new int[]{-1,-1}; } //采用滑动指针来判断多个相同的值区间 //滑动就要滑动两个边界 int left = index; int right = index; while (left - 1 >= 0 && nums[left-1] == nums[left]){     left--; } while (right + 1 < nums.length && nums[right+1] == nums[right]){     right++; } return new int[]{left,right};    }

利用二分法查找x的平方根

3. 力扣：查找x的平方根
   链接：https://leetcode-cn.com/problems/sqrtx

该题需注意int是的上下限和right+1问题

    public int mySqrt(int x) {    //根据目标函数进行划分界限 int left = 0; int right = x/2 + 1; while (right >= left){     long mid = left + (right - left)/2;     if (mid * mid == x ){  return (int) mid;     }else if (mid * mid > x){  right = (int) (mid - 1);     }else {  left = (int) (mid +1);     } } return right;    }

双指针（快慢指针）来移动或者删除元素

思想：慢指针指向重排的数组，快指针进行寻值，其实就是两个指针指向的值相互比较进行换值

1. 力扣：删除排序数组中的重复项
   链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

class Solution {    public int removeDuplicates(int[] nums) { int slowIndex = 1; for (int fastIndex = 1;fastIndex  < nums.length ;fastIndex++){     if (nums[fastIndex] != nums[fastIndex - 1]){  nums[slowIndex++] = nums[fastIndex];     } } return slowIndex;    }}

2. 力扣：移动零
   链接：https://leetcode-cn.com/problems/move-zeroes

//与上题思想一致class Solution {    public void moveZeroes(int[] nums) { int slowIndex = 0; for (int fastIndex = 0;fastIndex < nums.length; fastIndex++){     if (nums[fastIndex] != 0){  nums[slowIndex++] = nums[fastIndex];     } } while (slowIndex < nums.length){     nums[slowIndex++] = 0; }    }}

3. 力扣：有序数组的平方

class Solution {    public int[] sortedSquares(int[] nums) { int left = 0; int right = nums.length-1; int[] res = new int[nums.length]; int length = nums.length - 1; while (left <= right){     if (nums[left] * nums[left] < nums[right] * nums[right]){  res[length--] = nums[right] * nums[right];  right--;     }else {  res[length--] = nums[left] * nums[left];  left++;     } } return res;    }}

简谱吧