二分搜索 (opens new window)对于计算机相关专业的同学都不陌生。但是在找工作的过程中可能会有最熟悉的陌生人之感。

如果题目要求时间复杂度是O(log N)，那么我们首先应该往二叉堆,二叉树，二叉搜索上面想。

尽管二分查找的基本思想相对简单，但细节可以令人难以招架...

令人难以置信的是，这句话居然出自高德纳 (opens new window)之口.（PS:如果有人还没听说过此人，建议了解一下）

---

二分查找的一般前提条件是 数组有序

先来一道开胃菜 704. 二分查找 (opens new window)

题目描述:

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

(假设 nums 中的所有元素是不重复的)

我们一般经常这么写

public int search(int[] nums, int target){
    
    if(nums == null || nums.length == 0){
        return -1;
    }


    int left = 0;
    int right = nums.length -1;

    // 确认target是否在数组中。
    if(nums[right] < target || nums[left] < target){
        return -1;
    }

    while(left <= right){
        int mid = left +(right - left) / 2; // 至于mid值的获取技巧，不在讨论范围之内

        if(nums[mid] == target){
            return mid;
        }

        if(nums[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }

    return -1;
}

但是 二分搜索 (opens new window) 除了要求数组有序，基于数组的快速取值特性，我们还需要确定target是否在有序数组中

为什么有此一说呢？其实是因为这道题 702. 搜索长度未知的有序数组 - M (opens new window)

此题很有意思，严格满足二分搜索 (opens new window)的使用条件。但是不好下手。因为有序数组的长度未知。

无法确认右边界，这还怎么二分。

所以这道题的题眼其实就不只是二分搜索，而是如何确定右边界。只有确定了边界，加上数组有序的特性，使用二分搜索自然水到渠成。

class Solution {
    public int search(ArrayReader reader, int target) {
        if(reader.get(0) == target) return 0;

        int left = 0;
        int right = 1;

        // 查找右边界，这里更新左边界更加秒
        while(reader.get(right)< target){
            left = right;
            right *= 2;
        }

        while(left <= right){
            int mid = left + (right - left) / 2;

            if(reader.get(mid) > target){
                right = mid -1;
            }else if(reader.get(mid) < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }

        return -1;
    }
}

二分法的使用场景

1. 有序数组查找某个值;
2. 有序数组查找大于等于某个值的最左侧;
3. 有序数组查找小于等于某个值的最右侧;
4. 局部最值问题(涉及到局部有序);

需要我们注意的是二分是一种思想，并不是一定要严格排序的数组,一些部分排序的数组也可以使用二分思想。其核心是如何设置判定条件来缩小范围。

只要满足三岐性就可以使用二分法。

三歧性: 对于任何两个自然数n1和n2,或者n1大于n2,或者n2大于n1,或者n1等于n2,即“三歧性” (PS: IAW, 三岐性即存在大于小于等于的关系)

---

162. 寻找峰值 - M (opens new window)

峰值元素是指其值严格大于左右相邻值的元素

852. 山脉数组的峰顶索引- E (opens new window)

要求O(log N)的复杂度。要根据山脉数组的定义识别出来可以使用二分法。