---

前言

在信息技术的汹涌浪潮里，算法堪称驱动数据世界运转的核心引擎。而二分算法，恰似引擎中最精密的齿轮，凭借其精妙绝伦的设计，以一种简洁而又强大的方式，在浩如烟海的数据中实现高效目标定位。从互联网巨头的复杂推荐系统，到金融机构对海量交易数据的快速筛选，二分算法无处不在，它就像一位隐匿于幕后的超级英雄，默默为各种高效运作的系统保驾护航。此刻，让我们踏上探索二分算法的奇妙旅程，去深度解析这一算法背后的智慧，感受它如何重塑我们处理数据的方式。

那么什么是二分算法呢？

二分算法，也叫二分查找算法，是一种在有序数组中查找某一特定元素的搜索算法。其核心原理是通过不断将查找区间分成两半，逐步缩小目标元素可能存在的范围，直至找到目标元素或确定目标元素不存在。
比如，在一个从小到大排序的数组 [2, 4, 6, 8, 10, 12, 14] 中查找数字 8。首先，数组的起始索引为 0，末尾索引为 6，中间索引为 (0 + 6) / 2 = 3，此时中间元素是 8，正好与目标元素相等，查找成功。若要查找数字 5，第一次取中间元素 8，5 小于 8，所以下一次在左半部分数组 [2, 4, 6] 中查找，这部分数组起始索引 0，末尾索引 2，中间索引 (0 + 2) / 2 = 1，中间元素 4，5 大于 4，再在下半部分数组 [6] 中查找，最终确定 5 不在该数组中。二分算法每次迭代都能排除大约一半的数据，极大提高了查找效率，其时间复杂度为 O (log n) ，相比顺序查找的 O (n) 效率提升显著 。

接下来，本文将通过例题从而揭示展开二分算法的原理！

例题

一、二分查找

1.题目链接：二分查找
2. 题目描述：

给定⼀个 n 个元素有序的（升序）整型数组 nums 和⼀个⽬标值 target ，写⼀个函数搜索 nums 中 的 target，如果⽬标值存在返回下标，否则返回 -1。
⽰例 1:
输⼊: nums = [-1,0,3,5,9,12], target = 9
输出: 4 解释: 9 出现在 nums 中并且下标为 4
⽰例 2:
输⼊: nums = [-1,0,3,5,9,12], target = 2 输出: -1
解释: 2 不存在 nums 中因此返回 -1
提⽰：你可以假设 nums 中的所有元素是不重复的。 n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间

3. 算法流程：
   a. 定义 left ， right 指针，分别指向数组的左右区间。
   b. 找到待查找区间的中间点 mid ，找到之后分三种情况讨论：
   i. arr[mid] == target 说明正好找到，返回 mid 的值；
   ii. arr[mid] > target 说明 [mid, right] 这段区间都是⼤于 target 的，因此舍 去右边区间，在左边 [left, mid -1] 的区间继续查找，即让 right = mid - 1 ，然后重复 2 过程；
   iii. arr[mid] < target 说明 [left, mid] 这段区间的值都是小于 target 的，因 此舍去左边区间，在右边 [mid + 1, right] 区间继续查找，即让 left = mid + 1 ，然后重复 2 过程；
   c. 当 left 与 right 错开时，说明整个区间都没有这个数，返回 -1 。

4. 代码示例：

  public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid]<target)  left= mid+1;
            else right = mid;
        }
        return nums[left]==target?left:-1;
 }

二、在排序数组中查找元素的第一个和最后一个位置

1. 题目链接：在排序数组中查找元素的第⼀个和最后⼀个位置
2. 题目描述：

给你⼀个按照⾮递减顺序排列的整数数组 nums，和⼀个⽬标值 target。请你找出给定⽬标值在数组 中的开始位置和结束位置。 如果数组中不存在⽬标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
⽰例 1： 输⼊：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
⽰例 2： 输⼊：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
⽰例 3： 输⼊：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是⼀个⾮递减数组
-109 <= target <= 109

3. 算法思路：
   ⽤的还是二分思想，就是根据数据的性质，在某种判断条件下将区间⼀分为二，然后舍去其中⼀个 区间，然后再另⼀个区间内查找； 方便叙述，用 x 表示该元素， resLeft 表⽰左边界， resRight 表示右边界。
   寻找左边界思路：
   • 寻找左边界：
   ◦ 我们注意到以左边界划分的两个区间的特点：
   ▪ 左边区间 [left, resLeft - 1] 都是⼩于 x 的；
   ▪ 右边区间（包括左边界） [resLeft, right] 都是⼤于等于 x 的；
   • 因此，关于 mid 的落点，我们可以分为下⾯两种情况：
   ◦ 当我们的 mid 落在 [left, resLeft - 1] 区间的时候，也就是 arr[mid] < target 。说明 [left, mid] 都是可以舍去的，此时更新 left 到 mid + 1 的位置，继续在 [mid + 1, right] 上寻找左边界；
   ◦ 当 mid 落在 [resLeft， right] 的区间的时候，也就是 arr[mid] >= target 。 说明 [mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时 更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界；
   ◦ 当 mid 落在 [resLeft， right] 的区间的时候，也就是 arr[mid] >= target 。 说明 [mid + 1, right] （因为 mid 可能是最终结果，不能舍去）是可以舍去的，此时 更新 right 到 mid 的位置，继续在 [left, mid] 上寻找左边界；

• 由此，就可以通过⼆分，来快速寻找左边界

注意：这⾥找中间元素需要向下取整。

因为后续移动左右指针的时候：

• 左指针： left = mid + 1 ，是会向后移动的，因此区间是会缩⼩的；
• 右指针： right = mid ，可能会原地踏步（⽐如：如果向上取整的话，如果剩下 1,2 两个元 素， left == 1 ， right == 2 ， mid == 2 。更新区间之后， left，right，mid 的 值没有改变，就会陷⼊死循环）。
因此⼀定要注意，当 right = mid 的时候，要向下取整。

寻找右边界思路：

• 寻找右边界：
◦ ⽤ resRight 表示右边界；
◦ 我们注意到右边界的特点：
▪ 左边区间 （包括右边界） [left, resRight] 都是小于等于 x 的；
▪ 右边区间 [resRight+ 1, right] 都是⼤于 x 的； • 因此，关于 mid 的落点，我们可以分为下面两种情况：
◦ 当我们的 mid 落在 [left, resRight] 区间的时候，说明 [left, mid - 1]（ mid 不可以舍去，因为有可能是最终结果） 都是可以舍去的，此时更新 left 到 mid的位置；
◦ 当 mid 落在 [resRight+ 1, right] 的区间的时候，说明 [mid, right] 内的元素 是可以舍去的，此时更新 right 到 mid - 1 的位置；
• 由此，就可以通过⼆分，来快速寻找右边界；
注意：这⾥找中间元素需要向上取整。
因为后续移动左右指针的时候：
• 左指针： left = mid ，可能会原地踏步（比如：如果向下取整的话，如果剩下 1,2 两个元 素， left == 1， right == 2，mid == 1 。更新区间之后， left，right，mid 的值 没有改变，就会陷入死循环）。
• 右指针： right = mid - 1 ，是会向前移动的，因此区间是会缩小的； 因此⼀定要注意，当 right = mid 的时候，要向下取整。

⼆分查找算法总结：

请大家⼀定不要觉得背下模板就能解决所有⼆分问题。⼆分问题最重要的就是要分析题意，然后确定 要搜索的区间，根据分析问题来写出二分查找算法的代码。

4. 代码示例：

 public int[] searchRange(int[] nums, int target) {
        int[] dp = new int[2];
        dp[0] = dp[1] = -1;
        if(nums.length==0) return dp;
        int left = 0,right = nums.length-1;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid]<target){
                left = mid+1;
            }else{
               right = mid;
            }
        }
        if(nums[left] != target) return dp;
        else dp[0] = left;
            left = 0;
            right = nums.length-1;
        while(left<right){
             int mid  = left +(right-left+1)/2;
            if(nums[mid]<= target){
               left = mid;
            }else{
               right = mid -1;
            }
        }
         dp[1]= right;
         
        return dp;    
    }

三、搜索插入位置

1. 题目描述：搜索插入位置
2. 题目描述：

给定⼀个排序数组和⼀个⽬标值，在数组中找到⽬标值，并返回其索引。如果⽬标值不存在于数组 中，返回它将会被按顺序插⼊的位置。 请必须使⽤时间复杂度为 O(log n) 的算法。
⽰例 1:
输⼊: nums = [1,3,5,6], target = 5
输出: 2
⽰例 2:
输⼊: nums = [1,3,5,6], target = 2
输出: 1
⽰例 3:
输⼊: nums = [1,3,5,6], target = 7
输出: 4

3. 解法（⼆分查找算法）：
   算法思路：
   a. 分析插⼊位置左右两侧区间上元素的特点：
   设插入位置的坐标为 index ，根据插入位置的特点可以知道：
   • [left, index - 1] 内的所有元素均是小于 target 的；
   • [index, right] 内的所有元素均是⼤于等于 target 的。
   b. 设 left 为本轮查询的左边界， right 为本轮查询的右边界。根据 mid 位置元素的信 息，分析下⼀轮查询的区间：
   ▪ 当 nums[mid] >= target 时，说明 mid 落在了 [index, right] 区间上，mid 左边包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [left, mid] 上。因此，更新 right 到 mid 位置，继续查找。
   ▪ 当 nums[mid] < target 时，说明 mid 落在了 [left, index - 1] 区间上，mid 右边但不包括 mid 本身，可能是最终结果，所以我们接下来查找的区间在 [mid + 1, right] 上。
   因此，更新 left 到 mid + 1 的位置，继续查找。
   c. 直到我们的查找区间的长度变为 1 ，也就是 left == right 的时候， left 或者right 所在的位置就是我们要找的结果

4. 代码示例：

  public int searchInsert(int[] nums, int target) {
        int left = 0 ,right =nums.length-1;
        while(left<right){
            int mid = left+(right-left)/2;
            if(nums[mid]<target) left = mid+1;
            else right = mid;
        }
       if(nums[right]<target) return right+1;
       else return right;
    }

四、x 的平方根

1. 题⽬链接：x的平方根
2. 题⽬描述：

给你⼀个⾮负整数 x ，计算并返回 x 的 算术平方根 。 由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：输⼊： x = 4
输出： 2
示例 2：
输⼊： x = 8
输出： 2
解释：8 的算术平⽅根是 2.82842… , 由于返回类型是整数，小数部分将被舍去。

3. 解法（二分查找算法）：
   算法思路：
   设 x 的平方根的最终结果为 index ：
   a. 分析 index 左右两次数据的特点：
   ▪ [0, index] 之间的元素，平方之后都是小于等于 x 的；
   ▪ [index + 1, x] 之间的元素，平方之后都是⼤于 x 的。 因此可以使用二分查找算法。

4. 代码示例：

public int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        long left = 1;
        long right = x;
        while (left < right) {
            Long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return (int) left;
    }

五、山峰数组的峰顶

1. 题目链接： 山脉数组的峰顶索引
2. 题目描述：

符合下列属性的数组 arr 称为山脉数组 ：
• arr.length >= 3
• 存在 i（0 < i < arr.length - 1） 使得： ◦ arr[0] < arr[1] < … arr[i-1] < arr[i]◦ arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的⼭脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
⽰例 1：
输⼊： arr = [0,1,0]
输出： 1
⽰例 2：输⼊： arr = [0,2,1,0]
输出： 1
⽰例 3：输⼊： arr = [24,69,100,99,79,78,67,36,26,19]
输出： 2

3. 解法（二分查找）：
   算法思路：
   分析峰顶位置的数据特点，以及⼭峰两旁的数据的特点：
   ◦ 峰顶数据特点： arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；
   ◦ 峰顶左边的数据特点： arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是 呈现上升趋势；
   ◦ 峰顶右边数据的特点： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是 呈现下降趋势。
   因此，根据 mid 位置的信息，我们可以分为下⾯三种情况： ◦ 如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索； ◦ 如果 mid 位置呈现下降趋势，说明我们接下来要在 [left, mid - 1] 区间搜索； ◦ 如果 mid 位置就是⼭峰，直接返回结果。

4.代码示例：

  public int peakIndexInMountainArray(int[] arr) {
        int left = 0 ,right  =arr.length-1;
        while(left<right){
            int mid = left + (right-left)/2;
            if(arr[mid]<arr[mid+1]) left = mid + 1;
            else if(arr[mid]>arr[mid+1]) right = mid;
        }
        return left;
    }

六、搜索旋转排序数组中的最⼩值

1. 题目链接：寻找旋转排序数组中的最⼩值
2. 题目描述：

整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前， nums 在预先未知的某个下标 k（0 <= k <nums.length） 上进⾏了 旋 转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] （下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋 转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和⼀个整数 target ，如果 nums 中存在这个⽬标值 target ，则返回它的下标，否则返回 -1 。 你必须设计⼀个时间复杂度为 O(log n) 的算法解决此问题。
⽰例 1：输⼊： nums = [4,5,6,7,0,1,2], target = 0
输出： 4
⽰例 2：输⼊： nums = [4,5,6,7,0,1,2], target = 3
输出： -1
⽰例 3：输⼊： nums = [1], target = 0
输出： -1

3. 解法（二分查找）：
   算法思路：

题⽬中的数组规则如下

其中 C 点就是我们要求的点。
二分的本质：找到⼀个判断标准，使得查找区间能够⼀分为二。
通过图像我们可以发现， [A，B] 区间内的点都是严格⼤于 D 点的值的， C 点的值是严格小于 D 点的值的。但是当 [C，D] 区间只有⼀个元素的时候， C 点的值是可能等于 D 点的值 的。因此，初始化左右两个指针 left ， right ： 然后根据 mid 的落点，我们可以这样划分下⼀次查询的区间：
▪ 当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格⼤于 D 点的值，下⼀次查 询区间在 [mid + 1，right] 上；
▪ 当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格⼩于等于 D 点的值，下次查询区间在 [left，mid] 上。 当区间⻓度变成 1 的时候，就是我们要找的结果

4. 代码示例：

 public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int x = nums[nums.length - 1];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[right];
    }

七、 0〜n-1 中缺失的数字

1. 题目链接： 0〜n-1中缺失的数字
2. 题⽬描述：

⼀个⻓度为n-1的递增排序数组中的所有数字都是唯⼀的，并且每个数字都在范围0〜n-1之内。在范 围0〜n-1内的n个数字中有且只有⼀个数字不在该数组中，请找出这个数字。
⽰例 1:
输⼊: [0,1,3]
输出: 2
⽰例 2:
输⼊: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：1 <= 数组⻓度 <= 10000

3. 解法（⼆分查找算法）：
   算法思路：
   关于这道题中，时间复杂度为 O(N) 的解法有很多种，而且也是比较好想的，这里就不再赘述。 本题只讲解⼀个最优的二分法，来解决这个问题。 在这个升序的数组中，我们发现：
   ▪ 在第⼀个缺失位置的左边，数组内的元素都是与数组的下标相等的；
   ▪ 在第⼀个缺失位置的右边，数组内的元素与数组下标是不相等的。 因此，我们可以利用这个「二段性」，来使用「二分查找」算法。

4.代码示例：

 public int takeAttendance(int[] records) {
        int left = 0, right = records.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (records[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left == records[left] ? left + 1 : left;
    }

八、寻找峰值

1. 题目链接： 寻找峰值
2. 题目描述：

峰值元素是指其值严格⼤于左右相邻值的元素。 给你⼀个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何⼀个峰值所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
⽰例 1：
输⼊：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
⽰例 2：
输⼊：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。
提⽰：1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

3. 解法（二分查找算法）：
   算法思路： 寻找⼆段性： 任取⼀个点 i ，与下⼀个点 i + 1 ，会有如下两种情况：
   • arr[i] > arr[i + 1] ：此时「左侧区域」⼀定会存在山峰（因为最左侧是负无穷），那么我们可以去左侧去寻找结果；
   • arr[i] < arr[i + 1] ：此时「右侧区域」⼀定会存在山峰（因为最右侧是负无穷），那么我们可以去右侧去寻找结果。
   当我们找到「二段性」的时候，就可以尝试用「二分查找」算法来解决问题
4. 代码示例：

 public int findPeakElement(int[] nums) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > nums[mid - 1]) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

结语

本文到这里就结束了，主要介绍了二分查找算法，并解析了几道二分查找算法题目。希望能够对你有帮助。

以上就是本文全部内容，感谢各位能够看到最后，创作不易，希望大家多多支持！

最后，大家再见！祝好！我们下期见！