二分查找算法

时间:2024-10-02 14:37:11

目录

什么是二分查找

二分查找

题目链接

题目描述

思路分析

代码实现

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

题目链接

题目描述

思路分析

代码实现

x 的平方根

题目链接

题目描述

思路分析

代码实现

二分小结

山脉数组的峰顶索引

题目链接

题目描述

思路分析

代码实现

寻找旋转排序数组中的最小值

题目链接

题目描述

思路分析

代码实现

点名

题目链接

题目描述

思路分析

代码实现


什么是二分查找

二分查找是一种高效的搜索算法,适用于在一组数据中中查找某个特定元素,其基本思路是通过不断将查找范围减半来快速定位目标元素

接下来,我们就通过具体的问题,来学习二分查找

二分查找

题目链接

704. 二分查找 - 力扣(LeetCode)

题目描述

给定一个 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

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

思路分析

题目要求我们在 升序 数组 nums 中查找值为 target 的元素,若存在,返回该元素下标;若不存在,返回 -1

最简单的方法,就是使用 暴力枚举,遍历数组,判断每一个元素是否等于 target,若等于,则返回该下标值;若不等于,继续遍历。当遍历完数组仍未找到时,就返回 -1,此时的时间复杂度为 O(N)

但此时我们并没有利用到 数组是升序 的这个特性

在示例2中:

当遍历到 3 时,还是没有找到 target,但此时元素的值已经大于 target 了,由于数组是升序的,因此,后面的元素也都是大于 target 的,没有必要再继续遍历

此时,我们就可以进行优化:

遍历数组,判断每一个元素是否等于 target,若等于,则返回该下标值;若小于,继续遍历;若大于,直接返回 -1

再尝试进行优化:

当我们判断出 nums[i] 的值大于 target 时,直接就将 nums[i] 后面元素舍弃了,但当 nums[i] 小于 target 时,由于是从前向后进行遍历的,因此,每次都只舍弃了一个元素

若我们在数组中随机选取一个元素:

若 nums[i] 小于 target,说明 [0, nums[i] ] 区间内的元素(也就是 nums[i] 及其左边的元素)都小于 target,都可以直接舍弃,此时,我们就直接舍弃了一个区间内的元素,而不是一个元素

而若 nums[i] 等于 target,说明当前元素就是要找的值,直接返回下标即可

若 nums[i] 大于 target,说明 [ nums[i], nums.length - 1 ] 区间内的元素(也就是 nums[i] 及其右边的元素)都大于 target,都可以直接舍弃,此时,我们也直接舍弃了一个区间的元素

此时,我们就通过 nums[i] 将这个数组划分成了两个区间:  [0, nums[i] 和  [ nums[i], nums.length - 1 ] 

当 nums[i] 等于 target 时直接返回

当 nums[i] 小于 target 时,舍弃左边区间的元素

当 nums[i] 大于 target 时,舍弃右边区间的元素

那么,要如何确定 i 的位置呢?

在每次舍弃一个区间的元素时,我们都希望能够去掉更多的元素,但是我们并不能确定 nums[i] 和 target 的大小关系,因此,

若 左区间 > 右区间,舍弃右区间时舍弃的元素较少

若 左区间 <  右区间,舍弃左区间时舍弃的元素较少

因此,让 左区间 = 右区间,这样,无论舍弃左区间还是右区间,都能去掉一半的元素

也就是 让 i 处于中间位置

接着,要如何找到这个中间位置呢? 

要找到中间位置就需要知道左端点和右端点的位置,因此,定义 left 和 right 指针,分别指向区间的左端点和右端点,然后通过 left 和 right 计算出中点 mid 的位置,从而将数组划分为两个区间

 

然后根据 nums[mid] 的值进行判断:

若 nums[mid] = target,说明 nums[mid] 就是要找的元素,直接返回 mid 的值即可

若 nums[mid] > target,说明 [mid, right] 区间内的元素都大于 target,直接舍弃,继续在左边区间[left, mid - 1]进行查找,即 right = mid - 1,然后再继续查找

若 nums[mid] < target,说明 [left, mid] 区间内的元素都小于 target,直接舍弃,继续在右边区间 [mid + 1, right] 进行查找,即 left = mid + 1,然后继续查找

当 [left,right] 区间内元素个数为偶数时,此时,中间位置会有两个元素

在本题中,选取中间左边元素来划分区间 或 选取中间右边元素来划分区间都可以

选取中间左边元素来划分区间,左边区间内元素会比右边区间内元素少1

同理, 选取中间右边元素来划分区间,右边区间内元素会比左边区间内元素少1 

但并不会影响查找过程

最后,什么时候结束循环呢? 

 当 [left, right] 区间中只有一个元素时(也就是 left = right = mid),此时,仍需要判断这个元素是否等于 target,若不等于,则会移动 left 或 right,此时 left > right,区间不再存在,说明找不到值为 target 的元素,此时需要退出循环

因此,循环的结束条件为 left > right

在本题中,我们根据 数组升序 这个特性,选取了 中间元素,将数组划分为了两个区间,再通过 nums[mid] 和 target 的大小关系,选择性地舍弃了一部分元素,进而继续在另一部分区间内继续查找

上述查找方法也就是二分查找:

找到某个规律,选取某个元素将这个数组划分为两部分,根据规律选择性地舍弃一部分元素,进而继续在另一部分区间内继续查找

那么,二分查找的时间复杂度是多少呢? 

数组的大小为 n,最坏情况下查找了x 次

第一次查找后,剩余 n / 2 (\frac{n}{2^{1}})个元素

第二次查找后,剩余 n / 4(\frac{n}{2^{2}}) 个元素

第三次查找后,剩余 n / 8 (\frac{n}{2^{3}})个元素

...

第 x 次查找后,剩余 1(\frac{n}{2^{x}}) 个元素

x = {log_{2}}^{n}

因此,二分查找的时间复杂度为 log_{2}^{N}

接下来,我们就来尝试编写代码,解决问题

代码实现

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

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

题目链接

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

题目描述

给你一个按照非递减顺序排列的整数数组 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

思路分析

题目要求我们在非递减数组 nums 中找到 target 出现的开始位置结束位置,若不存在 target,则返回 [-1, -1]

最简单的方法就是遍历数组,找到 target 的开始和结束位置,但题目要求我们使用 时间复杂度为 O(log n) 的算法解决此问题

数组是非递减的,也就是有序的,因此,我们仍可以考虑使用二分查找,来解决本题:

根据数据的非递减性,将其划分为两个区间,然后舍去某个区间,进而在另一个区间查找

题目要求我们找到 target 出现的开始位置结束位置

我们首先来找开始位置

同样的,我们还是使用 left 和 right 分别标记区间的左端点和右端点,然后求 mid

 再判断 target 和 mid 的值

若 nums[mid]  <  target,表明 [left, mid] 区间内的所有元素都小于 target,不是我们要找的值,因此,都可以舍去,即 left = mid + 1

若 nums[mid] = target,此时直接返回吗?

当然不能,要找的是 target 出现的第一个位置,而mid 位置可能并不是第一个位置:

就如同上图所示,此时 mid 位置并不是 target 出现的第一个位置,但 mid 位置也可能是 target 出现的第一个位置,此时,并不能判断出 mid 是否为 target 出现的第一个位置,因此,不能直接返回,还要继续进行查找

但是,由于 nums[mid] = target,则 [mid + 1, right] 区间的值都大于等于 target,不是我们要找的第一个位置,因此,可以舍去[mid + 1, right] 区间内的所有元素,即 right = mid

若 nums[mid] > target, 表明[mid + 1, right] 区间内的元素都大于 target,不是我们要找的位置,因此,可以直接舍去,即 right = mid - 1

由于 nums[mid] = target 和 nums[mid] > target 的情况下,都会舍去右边区间[mid + 1, right]  的元素,因此,我们可以合并这两种情况,即 nums[mid] >= target,此时,可以舍去[mid + 1, right] 区间内的元素,即 right = mid

不能舍去 mid 位置的值,因为当 nums[mid] = target 时,该位置可能为 target 出现的第一个位置,因此不能舍去,还是通过后续的查找进行判断

当 [left,right] 区间内元素个数为偶数时,此时,中间位置会有两个元素

此时,我们应该选取哪个元素来划分区间呢?

我们要找到是 target 出现的第一个位置,此时,需要选择 中间左边元素 进行区间划分

若中间两个元素值相同,且都为 target

此时,我们选择左侧元素能够去掉更多的元素

此外,最重要的是,若我们选择选择右边元素划分区间,可能会出现死循环的情况

当我们在移动 left 和 right 时,

若 nums[mid] < target,left = mid + 1,left 向后移动,区间一定会缩小

若 nums[mid] >= target,right = mid,此时区间可能不会缩小

例如:

此时若我们选择 右边元素 来划分区间:

nums[mid] = target,right = mid,然后继续判断 nums[mid] = target,right = mid...

left、right 和 mid 的值不会改变,也就陷入了死循环

因此,在 [left, right] 区间内元素个数为偶数时,要选择中间左边元素进行区间划分,也就是在寻找中间元素时要向下取整(mid = (left + right) / 2)

那么,循环什么时候结束呢? 

left = right 为循环的结束条件,而不是 left > right

当 left = right 时,若数组中存在 target ,则此时 left(或 right)的位置就为 target 出现的第一个位置

若 继续判断,则会陷入死循环

当 left = right 时,mid = left = right,此时区间内只有一个元素,mid 位置的值一定大于等于 target,此时,若还要继续判断,则 right = mid,区间大小不会改变,left、right 和 mid 的位置不会改变,也就会一致循环判断下去,陷入死循环

总结一下寻找 target出现的第一个位置的思路:

(1)定义 left 和 right,指向区间的左端点和右端点,通过 left 和 right 确定 mid 的位置,当有两个中间元素时,要选取左边的中间元素,即 mid = (left + right) / 2

(2)判断 nums[mid] 和 target 的大小关系

若 nums[mid] < target,[left, mid] 区间内的元素都可以舍弃,left = mid + 1

若 nums[mid] >= target,[mid + 1, right] 区间内的元素可以舍弃,right = mid

(3)继续判断,直到 left = right

接下来,我们就继续找到 target 出现的最后一个位置

使用 left 和 right 分别标记区间的左端点和右端点,然后求 mid

 判断 target 和 mid 的值:

若 nums[mid]  >  target,则 [mid, right] 区间内(mid 及右边元素)的所有元素都大于 target,不是我们要找的值,因此,都可以舍去,即 right = mid - 1

若 nums[mid] <= target,则 [left, mid - 1] 区间内(mid 左边元素)的元素都小于等于 target,不是我们要找的值,都可以舍弃,即 left = mid

不能舍弃 mid ,mid 可能是要找的最后一个位置,因此不能舍弃,mid 还需要参与后续的判断

同样,当 [left,right] 区间内元素个数为偶数时,此时,中间位置会有两个元素

此时,我们需要选择 中间右边位置 的元素来划分区间,若我们选中中间左边元素来划分区间,可能会出现死循环

若 nums[mid] > target,right= mid - 1,right 向前移动,区间一定会缩小

若 nums[mid] <= target,left = mid,此时区间可能不会缩小

 如上图所示,此时 nums[mid] = target,left = mid,区间并不会缩小,left、right 和 mid 的位置并不会改变

因此,要选取中间右边元素来划分区间,也就是向上取整(mid = (left + right + 1) / 2)

循环什么时候结束呢? 

同样,left = right 为循环的结束条件,而不是 left > right

当 left = right 时,mid = left = right,此时区间内只有一个元素,mid 位置的值一定小于等于 target,此时,若还要继续判断,则 left = mid,区间大小不会改变,left、right 和 mid 的位置不会改变,也就会一致循环判断下去,陷入死循环

因此,当 left = right 时,循环结束,此时 left = right = mid,

若 target 存在,该位置就是 target 的结束位置,或是不存在 target 

总结一下寻找 target出现的第一个位置的思路:

(1)定义 left 和 right,指向区间的左端点和右端点,通过 left 和 right 确定 mid 的位置,当有两个中间元素时,要选取右边的中间元素,即 mid = (left + right + 1) / 2

(2)判断 nums[mid] 和 target 的大小关系

若 nums[mid] > target,[mid, right] 区间内的元素都可以舍弃,right = mid - 1

若 nums[mid] <= target,[left, mid - 1] 区间内的元素可以舍弃,left = mid

(3)继续判断,直到 left = right

接下来,我们就来尝试编写代码,解决问题 

代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        int len = nums.length;
        // 若数组中没有元素,直接返回
        if (len == 0) {
            return ret;
        }
        int left = 0, right = len - 1;
        // 查找第一个位置
        while(left < right) {
            int mid = (left + right) / 2;
             
            if(target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 判断  target 是否存在
        // 不存在,直接返回
        if (nums[left] != target) {
            return ret;
        }
        ret[0] = left;

        // 继续查找最后一个位置
        left = 0;
        right = len - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        ret[1] = left;
        return ret;
    }
}

x 的平方根

题目链接

69. x 的平方根 - 力扣(LeetCode)

题目描述

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

提示:

  • 0 <= x <= 231 - 1

思路分析

题目要求找到 x 的算术平方根,当其为小数时,只需要返回整数部分

我们可以通过暴力枚举来解决本题,依次枚举 0 到 x 之间的所有数 i,

若 i * i = x,直接返回 i

若 i * i > x,则返回 i - 1

class Solution {
    public int mySqrt(int x) {
        // 两个较大的数相乘,结果可能会超出 int 的最大范围
        for(long i = 0; i <= x; i++) {
            // i 的平方正好等于 x,直接返回 i
            if (i * i == x) {
                return (int)i;
            } else if (i * i > x) {
                // i 的平方大于 x,返回前一个数
                return (int)(i - 1);
            }
        }
        return -1;
    }
}

此时的时间复制度为 O(N)

我们还可以通过二分查找来找到 x 的算术平方根

我们需要找到某个元素,将数组划分为两个区间,然后舍去某个区间,进而在另一个区间查找

 x 的平方根为 i,则 i 可以将数据划分为两个区间

[0, i]:平方之后都是小于等于 x 的

[i + 1, x]:平方之后都是大于 x 的

所有的数据看做是一个数组,定义 left 和 right 分别指向数组的左右两端点(也就是 0 和 x):

此时,就可以通过 left 和 mid 找到中间位置 mid

判断 mid 的平方和 x 之间的关系:

若 mid * mid > x,则 [mid, x] 之间的数据平方和都大于 x,都可以舍弃,即 right = mid - 1

若 mid * mid <= x,则 [left, mid - 1] 之间的数据平方和都小于 x,都可以舍弃,即 left = mid

mid 不能舍弃,因为 mid 可能就是要找的平方根,还需要通过后续的判断才能决定是否舍弃

直到 left = right,循环结束,此时 left = right = mid,mid 的值就是 x 的平方根

当 [left, right] 区间内的元素个数为偶数时,此时该选择中间左边的元素还是中间右边的元素来划分区间呢?

我们还是来进行分析: 

 

若选择左边位置来划分,此时 mid * mid = x,left = mid,区间大小不变,也就意味着会陷入死循环

而选择右边位置来划分,此时 mid * mid > x,right = mid - 1,区间减小,继续判断

因此,应该选择中间右边位置来划分区间,也就是 mid = (left + right + 1) / 2 

代码实现

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

通过上述三道题,我们对二分查找也有了基本的认识,接下来,我们就先来总结一下二分查找的使用

二分小结

首先,我们得分析清楚什么时候能够使用二分查找?

要使用二分查找,我们得找到题目中的某个规律,选取某个元素将数据划分为两部分,根据规律选择性地舍弃一部分元素,进而继续在另一部分区间内继续查找

即:

(1)分析清楚能否通过某个元素将数据划分为两部分,若可以,就可以考虑使用二分查找

(2)判断能否通过这个元素选择性地舍弃一部分元素,进而在另一部分区间内继续查找

若满足以上两点,就可以使用二分查找,接着就需要处理二分查找的细节问题

定义 left 和 right 指向区间的左右端点,当区间内元素个数为奇数时,mid 的值为中间的元素

但当区间内元素个数为偶数时,中间就会有两个元素,此时,该选择哪个元素来划分区间呢?

由于区间划分的不同,在移动 left 和 right 也会有所不同,此时,划分区间的元素也就不同:

(1)当区间划分为 [left, mid] [mid, right] 和 mid 时,若 mid 满足条件,则可以直接退出循环,而当不满足条件时,可直接舍弃左半部分 [left, mid] 区间(mid 及其左边所有元素)或是右半部分 [mid, right](mid 及其右边所有元素),即 left = mid + 1 right = mid - 1,无论哪种情况,都会让区间减小,进而在更小的区间内继续查找

(2)当区间划分为 [left, mid] [mid + 1, right] 时,也就是要寻找满足条件的第一个元素(也就是左端点)

可能会舍弃左半部分[left, mid]区间(mid 及其左边所有元素)left = mid + 1,或是舍弃右半部分[mid + 1, right](mid 右边所有元素,不包括 mid)right = mid,在舍弃右半部分元素(right = mid)时,可能会出现区间不变的情况,也就可能会出现死循环,因此,需要选择中间左边元素(mid = (left + right) / 2)来划分区间,防止出现死循环,在这种情况下,找到的是满足条件的第一个元素

(3)当区间划分为 [left, mid - 1] [mid, right] 时,也就是要寻找满足条件的最后一个元素(也就是右端点)

此时,可能舍弃左半部分 [left, mid - 1] 区间(mid 左边所有元素,不包括 mid)left = mid,或是舍弃右半部分 [mid, right](mid 及其右边所有元素)right = mid - 1,在舍弃左半部分元素(left = mid)时,可能会出现区间不边的情况,也就有可能会出现死循环,因此,需要选择中间右边元素(mid = (left + right + 1) / 2)来划分区间,防止出现死循环,在这种情况下,找到的是满足条件的最后一个元素

即:

(1) mid 将区间划分为三个部分:[left, mid] [mid, right] 和 mid ,right = mid - 1,left = mid + 1,选择左边元素或右边元素都可以

(2)mid 将区间划分为两个部分:[left, mid] 和 [mid + 1, right],查找左端点,right = mid,left = mid + 1 需要选择左边元素(mid = (left + right) / 2)来划分区间

(3)mid 将区间划分为两个部分:[left, mid - 1] 和 [mid, right],查找右端点,right = mid - 1,left = mid ,需要选择右边元素(mid = (left + right + 1) / 2)来划分区间

总而言之,我们需要根据具体的情况来判断查找的是哪个元素,从而划分区间,根据划分区间的不同,确定 left 和 right 是如何移动的,从而确定选择哪个元素来进行划分

循环结束的条件是什么呢?

当 left = right 时循环结束,还是 left > right?

此时也需要分情况讨论:

mid 将区间划分为三个部分:[left, mid] [mid, right] 和 mid 时,当 [left, right] 区间中只有一个元素时(也就是 left = right = mid),此时,仍需要判断这个元素是否满足条件,若不满足,则会移动 left 或 right,此时 left > right,区间不再存在,说明没有满足条件的元素,此时需要退出循环,因此,循环的结束条件为 left > right

而 mid 将区间划分为两个部分时,([left, mid] 和 [mid + 1, right] )或是 ([left, mid - 1] 和 [mid, right])时,当 [left, right] 区间内只有一个元素时(left = right = mid)时,区间内的最后一个元素就是要找的结果(或是没有满足条件的元素),若此时再继续判断,就会陷入死循环,因此,循环结束的条件为 left = right

求 mid 的细节

在前面,我们在确定 mid 的取值时,使用 mid = (left + right) / 2 或是 mid = (left + right + 1) / 2,但是当 left 和 right 的值都很大时,left + right 可能会溢出,因此,可以使用 mid = left + (right - left) / 2 mid = left + (right - left + 1) / 2 来防止溢出

最后,我们来总结一下三种划分情况的二分模板:

(1)[left, mid] [mid, right] 和 mid

 while (left <= mid) {

        int mid = left + (right - left) / 2; // 或是 mid = left + (right - left) / 2;

        if(...) {

                left = mid + 1; // 舍弃左区间

        } else if(...) {

                right = mid - 1; // 舍弃右区间

        } else {

                break; // 满足条件,该元素就是要找的元素

        }

}

(2)[left, mid] 和 [mid + 1, right],right = mid,left = mid + 1,求左端点

 while (left < mid) {

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

        if(...) {

                left = mid + 1; // 舍弃左区间

        } else if(...) {

                right = mid; // 舍弃右区间

        }

}

(3) [left, mid - 1] 和 [mid, right],left = mid, right = mid - 1,求右端点

 while (left <= mid) {

        int mid = left + (right - left + 1) / 2;

        if(...) {

                left = mid; // 舍弃左区间

        } else if(...) {

                right = mid - 1; // 舍弃右区间

        }

 接下来,我们就通过更多了练习来进一步熟悉二分查找的使用

山脉数组的峰顶索引

题目链接

852. 山脉数组的峰顶索引 - 力扣(LeetCode)

题目描述

给定一个长度为 n 的整数 山脉 数组 arr ,其中的值递增到一个 峰值元素 然后递减。

返回峰值元素的下标。

你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。

示例 1:

输入:arr = [0,1,0]
输出:1

示例 2:

输入:arr = [0,2,1,0]
输出:1

示例 3:

输入:arr = [0,10,5,2]
输出:1

提示:

  • 3 <= arr.length <= 105
  • 0 <= arr[i] <= 106
  • 题目数据 保证 arr 是一个山脉数组

思路分析

给定的山脉数组中的值会递增到一个峰值元素,然后递减

题目要求我们找到这个峰值元素并返回,且实现时间复杂度为 O(log(n)) 的解决方案

 我们考虑能能否使用 二分查找:

(1)能否通过某个元素将数组分为两个区间?

假设峰值元素的下标为 i:

峰值元素左边的元素都小于 i,呈现上升趋势

峰值元素右边的元素都大于 i,呈现下降趋势

可以将数组划分为两个区间

(2)能否通过 arr[i] 选择性地舍弃一部分元素,进而在另一部分区间内继续查找?

mid 将数组划分为两个区间:[left, mid] 和 [mid + 1, right] 

 可以通过数组中元素呈现的趋势来舍弃区间:

若 mid 位置元素呈现下降趋势(mid 右边元素位于 [mid + 1, right] 区间),则舍弃 [mid + 1, right] 区间内元素,right = mid,继续在 [left, mid] 区间内查找

若 mid 位置元素呈现上升趋势(mid 及左边元素位于 [left, mid] 区间),则舍弃 [left, mid] 区间内元素,left = mid + 1,继续在 [mid + 1, right] 区间内查找

循环查找,直到 left = right = mid,,此时 left 位置的元素就是下降区间内的第一个元素

mid 将数组划分为 [left, mid] 和 [mid + 1, right] 两个区间,left = mid + 1,right = mid,需要选择中间左边元素来划分区间

接下来,我们就来尝试编写代码,解决问题

代码实现

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int len = arr.length;
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < arr[mid + 1]) {
                // 呈上升趋势
                left = mid + 1;
            } else {
                // 呈下降趋势
                right = mid;
            }
        }
        return left;
    }
}

由于本题中要查找的元素只有一个,因此也可以将数组划分为 [left, mid - 1] 和 [mid, right] 来查找上升区间内的最后一个元素

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int len = arr.length;
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid] > arr[mid - 1]) {
                // 呈上升趋势
                left = mid;
            } else {
                // 呈下降趋势
                right = mid - 1;
            }
        }
        return left;
    }
}

寻找旋转排序数组中的最小值

题目链接

153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

题目描述

已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

  • 若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

给你一个元素值 互不相同 的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。

示例 2:

输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 3 次得到输入数组。

示例 3:

输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。

提示:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums 中的所有整数 互不相同
  • nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋

思路分析

长度为 n 的数组,原按照升序排列,每次旋转都会将数组的第一个元素旋转到数组的最后位置,题目要求我们找到旋转之后数组的最小元素

我们通过一个具体的例子来分析题目

数组旋转前是按照升序排列的,也就是呈现上升趋势:

旋转后,就将其分成了两部分

 

通过上图,我们可以发现:旋转到数组最后的元素也呈现上升趋势

而后半段数据中的第一个元素,也就是我们要找的最小值

因此,我们可以将数组分为两个区间:

左边区间的元素都大于数组的最后一个元素

右边区间的元素都小于等于数组的最后一个元素

定义 left 和 right 指向区间的左右端点,通过 left 和 right 确定 mid

当 mid 落在左边区间时,[left, mid] 内的元素都大于数组的最后一个元素,都可以舍弃,left = mid + 1

当 mid 落在右边区间时,[mid, right] 内的元素都小于等于数组的最后一个元素,mid 最小,因此,可以舍弃 [mid + 1, right] 区间内的元素,right = mid

循环判断,直到循环结束

此时,left 位置元素就是被旋转到后面元素中的第一个元素

此时,left = mid + 1,right = mid,因此,mid = left + (right - left) / 2

接下来,我们就来编写代码,解决问题

代码实现

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

点名

题目链接

LCR 173. 点名 - 力扣(LeetCode)

题目描述

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席,请返回他的学号。

示例 1:

输入: records = [0,1,2,3,5]
输出: 4

示例 2:

输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

提示:

1 <= records.length <= 10000

思路分析

题目要求我们找到数组中缺失的数字

若没有同学缺失,数字中的元素是 0 - n - 1,也就意味着数组中的元素和下标是一一对应的(相同的)

但由于有一位同学缺失,那么,在这个同学缺失后,后面的元素和下标也就是不对应(不相同)的

因此,我们就可以通过这个缺失的元素 target,将数据分为两份:

target 左边的元素和下标是相同的

target 右边的元素和下标是不相同的 

因此,我们可以通过二分查找,找到元素和下标不相同的第一个元素

定义 left 和 right,确定 mid 的值

若 mid = nums[mid],则 [left, mid] 区间内所有元素都和下标相等,没有缺失的元素,舍弃,left = mid + 1

若 mid != nums[mid],则 [mid, right] 区间内所有元素都和下标不相等,且 mid 是第一个,因此,[mid + 1, right] 区间内的所有元素都可以舍弃,right = mid

继续判断,直到循环结束

此时,left = mid + 1,right = mid,因此,mid = left + (right - left) / 2

接下来,我们就来编写代码,解决问题

代码实现

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