刷题笔记 - 二分查找 - 《数据结构》

例题2
参考资料

如果对时间复杂度的要求有 log，通常都需要用到二分查找
二分查找规则:

左闭右闭[left, right]
左闭右开[left, right)

二分法最重要的两个点：

while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right
迭代过程中 middle 和 right 的关系，到底是 right = middle - 1 还是 right = middle
真正影响的是中间那个数字到底该不该加入下一次的查找中，也就是边界问题

二分查找需要的条件:

用于查找的内容逻辑上来说是需要有序的
查找的数量只能是一个，而不是多个(也有多个的情况，需要进行处理，LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置)

示例:

左闭右闭[left, right] 注意：int right = size-1;

int search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是需要查找的值
{
  int left = 0;
  int right = size - 1;    // 定义了target在左闭右闭的区间内，[left, right]
  while (left <= right) {    //当left == right时，区间[left, right]仍然有效
      int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，防止溢出
      if (nums[middle] > target) {
          right = middle - 1;    //target在左区间，所以[left, middle - 1]
      } else if (nums[middle] < target) {
          left = middle + 1;    //target在右区间，所以[middle + 1, right]
      } else {    //既不在左边，也不在右边，那就是找到答案了
          return middle;
      }
  }
  //没有找到目标值
  return -1;
}

左闭右开[left, right) 注意：int right = size;
```java int search(int nums[], int size, int target) { int left = 0; int right = size; //定义target在左闭右开的区间里，即[left, right) while (left < right) { //因为left = right的时候，在[left, right)区间上无意义
```
  int middle = left + ((right - left) / 2);
  if (nums[middle] > target) {
      right = middle; //target 在左区间，在[left, middle)中 
  } else if (nums[middle] < target) {
      left = middle + 1;
  } else {
      return middle;
  }
```
} // 没找到就返回-1 return -1; }

<a name="ie6nO"></a>
## 例题1
```java
public class No35搜索插入位置 {
    public static void main(String[] args) {
        int[] nums = {1,3,5,6};
        System.out.println(searchInsert(nums,7));
    }

    public static int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int l=0,r=n-1;
        int mid = (l+r)/2;
        while(l<r){  
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                r = mid;
            }else {
                l = mid+1;  //左边进位 +1
            }
            mid = (l+r)/2;
        }
        if(nums[n-1] < target){
            mid = n;
        }
        return mid;
    }
}

例题2

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0,right = nums.length-1;

        while(left < right){
            int mid = (left+right)/2;
            if(nums[mid] == nums[mid^1]){
                left = mid+1;
            }else {
                right = mid;
            }
        }
        return nums[left];
    }
}

二分查找

例题2

参考资料