Leetcode / 二分查找

有序数组要想到二分查找

int left = 0;
int right = nums.length-1;
while(left <= right){ // l = r 处理只有一个元素的情况;如果超时条件改为left < right
    int mid = low + (high - low) / 2;
        //low+high在low和high特别大时可能溢出，使用减法low + (high - low)/2避免溢出
    if(target = nums[mid]){
        return mid;
    }
    else if(target > nums[mid]){
        left = mid+1; // 根据题目注意区间开闭
    }else if(target < nums[mid]){
        right = mid -1;
    }
    return -1;
}

• 简单

  374 猜数字大小
  278 第一个错误的版本

• 二分

  35 搜索插入位置
  34 / 剑指 53 在排序数组中查找元素的第一个和最后一个位置(存在重复元素)(二分+中心扩散)
  剑指53 - II. 0～n-1中缺失的数字
  540 有序数组中的单一元素
  167 两数之和 II - 输入有序数组（二分）

• 旋转数组

  189 旋转数组
  33 搜索旋转排序数组(无重复元素，两个区间必有一个有序)
  81 搜索旋转排序数组 II(有重复元素，可能出现无法判断哪个区间有序的情况，num[l] = num[mid] = num[r]。解决方法：将当前二分区间的左边界加一，右边界减一。)
  153 寻找旋转排序数组中的最小值(无重复元素)(几处细节)
  154 / 剑指11 寻找旋转排序数组中的最小值 II (有重复元素)

• 数学

  367 有效的完全平方数
  69 x 的平方根
  275 H 指数 II(给定一个大小为 n 的升序的引用次数列表，要求找到满足 citations[i] >= n - i 的第一个 citations[i])
  441 排列硬币(等价于求满足k(k + 1) <= 2n的k的最大值，二分法可以设置左边界为0，右边界设置为√2n，然后二分查找即可)
  162 寻找峰值

     /\
    /  \
   /    \
  /      \
  
  二分时，取到的 中间值，与 中间值+1 做对比。有2种情况：
  中间值 < 中间值+1 ：说明当前取的点，在 上坡 部分，峰顶值在前面
  中间值 > 中间值+1 ：说明当前取的点，在 下坡 部分，峰顶值在后面
  
  二分法 第一次 mid 是有2层意义：
  第一次 mid 的点，一定会落到一座山上；并判断当前是处在上坡，还是下坡
  

时间复杂度：$O(logN)$，远好于顺序查找的$O(n)$
（虽然二分查找效率高，但是要将表按关键字排序。而排序本身很费时）