AlgorithmBinary Search

Binary Search

Binary Search, 二分法
Views:

Coding时的主要问题

  • 循环结束条件到底如何选
    • left <= right;
    • left < right;
    • left + 1 < right;
  • 指针变化
    • left或right = mid;
    • left或right = mid + 1;
    • left或right = mid - 1;

如果不能妥善处理上述问题，就很容易导致死循环

通用的二分法模板

为了解决上述问题，可采用如下二分法模板

  • 循环结束条件：永远是 left + 1 < right; 也就是说当left和right指针相邻时则循环结束退出
  • 指针变化：永远是 left或right = mid;
  • 永远采取下中位数 mid = left + (right - left)/2 同时避免越界访问
  • 永远分三段式判断来移动指针：array[mid] ==/</> taret？
  • 循环结束后永远double check：array[left] == target? array[right] == target?

Example

给定有序数组和target，寻找target在数组中第一次出现的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0) return res;
        int left = 0, right = nums.length - 1;
        //相邻则退出
        while(left + 1 < right){
            //下中位数，同时注意形式防止溢出
            int mid = left + (right - left)/2;
            //三段式判断
            if(nums[mid] < target)
                left = mid;
            else if(nums[mid] == target)
                right = mid;
            else if(nums[mid] > target)
                right = mid;
        }
        //double check
        if(nums[left] == target) return left;
        if(nums[right] == target) return right;
        return -1;
    }
}

解题三种思路

  • OOOOXXXX –> 常见于有序数组中的search，找到满足某个条件的值第一个位置或最后一个位置
  • Half Half –> 给定数组通常乱序或不是传统有序，无法找到一个条件形成上述模型，则可根据判断，保留有解的一半，去掉无解的一半
  • Result –> 当题目没有给出数组或者很难看出可用二分法时，可尝试对目标值进行二分，同样是找到满足某个条件的最大最小值。此类问题一般会有别的方法，但是如果用二分显然会更简单。

常见题型

Share