二分查找习题篇(下)

1.山脉数组的峰顶索引

题目描述：

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

解法一：暴力枚举 O(N)

算法思路：

根据峰顶值的特点（比两侧元素都要大），遍历数组内的每一个元素，找到一个比左右两边元素都大的元素即可。

代码实现：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) 
    {
        int n = arr.size();
        // 遍历数组内每⼀个元素，直到找到峰顶
        for (int i = 1; i < n - 1; i++) 
            // 峰顶满⾜的条件
            if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
            	return i; 
        // 为了处理 oj 需要控制所有路径都有返回值
        return -1;
    }
};

解法二：二分查找算法

算法思路：

由题意我们可以将数组分为两部分，以峰顶值元素i为界，i左边区域是arr[i]>arr[i-1],i右边区域是arr[i]<arr[i-1]。即具有“二段性”，可以用二分查找。

算法流程：

1.令left=0,right=arr.size()-1;

2.当left<right时，下列一直循环：

找到待查找区间的中间点 mid ，找到之后分两种情况讨论：

当arr[mid]>arr[mid-1],说明mid处于i的左边区域，更新left=mid;
当arr[mid]<arr[mid-1],说明mid处于i的右边区域，更新right=mid-1.

代码实现：

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr)
     {
        int left=0,right=arr.size()-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;
    }
};

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。

算法思路：

看题，我们可以直到这道题和上一道题很像；区别在于在上一题中，所给的数组是一个山脉数组，而这道题是无序的。

由题意我们可以将数组分为两部分，以峰顶值元素i为界。

当nums[i]>nums[i+1]时，在[i,i+1]呈现一个下降的趋势。而nums[-1]=-∞,所以，i的左边区域一定会有一个峰顶值；而nums[n] = -∞，所以，i的右边区域不一定存在峰顶值。
当nums[i]<nums[i+1]时，在[i,i+1]呈现一个上升的趋势。我们同理可以确定，i的左边区间不一定存在峰顶值，但i的右边区间一定会存在一个峰顶值。

由此可见，数组具有“二段性”，可以用二分查找。

算法流程：

1.令left=0,right=nums.size()-1;

2.当left<right时，下列一直循环：

找到待查找区间的中间点 mid ，找到之后分两种情况讨论：

当nums[mid]>nums[mid+1],此时mid处于i的左边区域，左区域一定会存在山峰，更新right=mid,在左区域去寻找结果；
当nums[mid]<nums[mid+1],此时mid处于i的右边区域，右区域一定会存在山峰，更新left=mid+1,在右区间去寻找结果。

代码实现：

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

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

题目描述：

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

解法一：暴力查找最小值 O(N)

解法二：二分查找算法

算法思路：

二分的本质：找到一个判断标准，使得查找区间能够一分为二。

题目中的数组的规律如下：

在这里插入图片描述

通过观察，可以知道输入数组nums具有“二段性”，所以可以用二分查找算法解题。

在这幅图中，C点即数组中我们所求的最小元素。

[A~B] : nums[i]>nums[n-1];

[C~D] : nums[i]<=nums[n-1].

算法流程：

left =0， rightright=nums.size()-1;

当left<right时，下列一直循环：

找到待查找区间的中间点 mid ，找到之后分三种情况讨论：

在[A，B] 中，满足nums[mid]>nums[n-1]，下次循环时需要更新left=mid+1;

在[C，D] 中，满足nums[mid]<=nums[n-1]，下次循环时需要更新right=mid;

当left=right，区间长度变成1，这时就是我们要找的结果。

代码实现：

class Solution {
public:
    int findMin(vector<int>& nums) 
    {
        int left=0,right=nums.size()-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[left];      
    }
};

4.0〜n-1中缺失的数字

题目描述：

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

算法思路：

本题有多种时间复杂度为O(N)的解法：

哈希表
直接遍历找结果
位运算
数学（高斯求和公式）

算法优化：

在这个升序的数组中，我们发现：

在缺失位置的左边，数组内的元素都是与数组的下标相等的；

在缺失位置的右边，数组内的元素与数组下标是不相等的。

因此，本题数组具有“二段性”，可以用二分查找算法解题。

算法流程：

1.令left=0,right=nums.size()-1;

2.当left<right时，下列一直循环：

找到待查找区间的中间点 mid ，找到之后分两种情况讨论：

mid在缺失位左边：nums[mid]==mid，更新left=mid+1;

mid在缺失位右边：nums[mid]!=mid，更新right=mid.

细节处理：要是循环完，没有缺失的元素，那么缺失的就是最后一个元素

代码实现：

class Solution {
public:
    int takeAttendance(vector<int>& records) 
    {
        int left=0,right=records.size()-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;
    }
};