二分查找算法

定义（来源维基百科）

在计算机科学中，二分查找算法，也称折半搜索算法、对数搜索算法。是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

知识点拆分

二分查找	理解	自己出题	别人出题
有序数组	[1, 2, 3, 4] [1, 1, 1, 2, 2, 2]	升序 降序 升序（含重复元素） 降序（含重复元素）	相邻两个元素之间两两有序
查找某一特定元素	一个具体的数字，例如0, 1, 2	给出具体的数字	不给你具体的数字，而是告诉你要查找的数具有某种性质

代码模板

网上二分的模板一堆，各家有各家的说法，但我觉得[acwing](常用代码模板1——基础算法 - AcWing)的模板是比较好的，因为它只有两个，网上分：左闭右开等等… 太复杂了

这两个模板必须确保 l 和 r 在区间的两个端点，不能在答案之外，也即，左边右闭

1. 整数二分

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2. 浮点数二分

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度，取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

作者：yxc
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度

• 时间复杂度：最坏$O(logn)$ ，最优$O(1)$ ，平均时间复杂度$O(logn)$
• 空间复杂度：$O(1)$

题目

1. 704. 二分查找 - 力扣（LeetCode）

2. 34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

3. 35. 搜索插入位置 - 力扣（LeetCode）

4. 162. 寻找峰值 - 力扣（LeetCode）

5. 153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

6. 33. 搜索旋转排序数组 - 力扣（LeetCode）

7. 154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）

题目Java代码参考

• 704 题参考代码

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[l] == target ? l : -1;
    }
}

• 34题参考代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = {-1, -1};
        if (nums.length == 0) return ans;
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] == target) {
            ans[0] = l;
            l = 0;
            r = nums.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            ans[1] = r;
            return ans;
        } else return ans;
    }
}

• 35题参考代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[r] >= target) return r;
        else return r + 1;
    }
}

• 162题参考代码

class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > nums[mid - 1]) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}

• 153题参考代码

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > nums[0]) l = mid;
            else r = mid - 1;
        }
        return nums[(r + 1) % n];
    }
}

• 33题参考代码

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        int mid = 0;
        while (l < r) {
            mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        if (target >= nums[0]) l = 0;
        else {
            l++;
            r = n - 1;
        }

        while (l < r) {
            mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[r] == target) return r;
        else return -1;
    }
}

• 154题参考代码

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (r >= 0 && nums[0] == nums[r]) r--;
        if (r == 0) return nums[0];
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        return nums[(r + 1) % n];
    }
}

总结

二分查找的作用时可以在 $O(logn)$ 的时间复杂度内查找某一特定元素，使用二分的前提条件是有序性。
查找特定元素可以是具体的，也可以是抽象的（具有某种性质）。
有序性可以是相邻两个元素之间有序。