[算法] 优先算法(六):二分查找算法(下)

个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
️热门专栏:
Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
Java EE(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~

5. 山峰数组的峰顶(难度:1度)

OJ链接

• 题目描述

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

• 算法原理

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] && arr[i] > arr[i + 1] ，也就是呈现下降趋势。
2. 因此，根据mid 位置的信息，我们可以分为下⾯三种情况：
   ◦ 如果mid 位置呈现上升趋势，说明我们接下来要在[mid + 1, right] 区间继续搜索；
   ◦ 如果mid 位置呈现下降趋势，说明我们接下来要在[left, mid - 1] 区间搜索；
   ◦ 如果mid 位置就是山峰，直接返回结果。
   [细节问题] 由于两个山脚一定不是山顶,所以直接从第二个和倒数第二个元素开始.

• 代码实现

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

这道题需要注意的地方是,如果使用向下取整,在条件判断的时候,只能使用arr[mid-1] < arr[mid],不可以使用arr[i] < arr[i + 1],因为在取值的时候,很可能正好取到峰值,这时候left不会更新,right也会更新到mid的前一个值,此时返回值就不准确.

6. 搜索旋转排序数组中的最小值(难度:2度)

• 题目描述

已知一个长度为 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 次得到输入数组。

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

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

[注意] 本题如果以D为分界点的话,只能使用向上取整,因为[A,B]区间都是大于D的,没有等于的地方.

7. 点名(难度:1度)

• 题目描述

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席，请返回他的学号。
示例 1:
输入: records = [0,1,2,3,5]
输出: 4
示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7

• 算法原理
  本题只讲解⼀个最优的⼆分法，来解决这个问题。
  在这个升序的数组中，我们发现：
  ▪ 在第⼀个缺失位置的左边，数组内的元素都是与数组的下标相等的；
  ▪ 在第⼀个缺失位置的右边，数组内的元素与数组下标是不相等的。
  因此，我们可以利用这个「⼆段性」，来使用「⼆分查找」算法
  这道题最重要的是找到下标与数据的关系,才比较容易看出这道题的二段性.
• 代码实现

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

8. 寻找峰值(难度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。

• 算法原理
  这道题与第5题的不同就是,这道题就是一个普通的数组中寻找最大值,而第5题是在一个山峰数组中寻找最大值,也就是说这道题有可能取到0,和最后一个位置的值.其他与第五题完全相同.
• 代码实现

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