[Algorithm][二分查找][山峰数组的峰顶索引][寻找峰值][寻找旋转排序数组中的最小值][0~n-1中缺失的数字]详细讲解

1.山脉数组的峰顶索引

1.题目链接

• 山脉数组的峰顶索引

2.算法原理详解

• 数据虽然不是严格有序，但是仍具有二段性，可以用二分查找
  • 本题可以印证：即使数据无序，只要符合二段性，就可以使用二分查找
    

3.代码实现

int PeakIndexInMountainArray(vector<int>& arr) 
{
    int left = 1, right = arr.size() - 2;
    while(left < right)
    {
        int mid = left + (right - left + 1) / 2;
        if(arr[mid] >= arr[mid - 1])
        {
            left = mid;
        }
        else
        {
            right = mid - 1;
        }
    }

    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.寻找峰值

1.题目链接

• 寻找峰值

2.算法原理详解

• 本题虽然在数据上，是明显的无序，但是仍然可以找到二段性的存在，可以使用二分查找

  • 本题可以印证：即使数据无序，只要符合二段性，就可以使用二分查找
    

• 任取⼀个点mid，与下⼀个点mid + 1，会有如下两种情况：

  • arr[mid] > arr[mid + 1]
    • 此时「左侧区域」⼀定会存在⼭峰(因为最左侧是负⽆穷)，那么可以去左侧去寻找结果
  • arr[mid] < arr[mid + 1]
    • 此时「右侧区域」⼀定会存在⼭峰(因为最右侧是负⽆穷)，那么可以去右侧去寻找结果
      

3.代码实现

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

1.题目链接

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

2.算法原理详解

• 二分的本质：找到一个判断标准，使得查找区间能够一分为二
• 通过图像可以发现，[A，B]区间内的点都严格> D点的值，C点的值严格< D点的值
  • 但是当[C，D]区间只有⼀个元素的时候， C点的值可能= D点的值
    

3.代码实现

int findMin(vector<int>& nums) 
{
    int n = nums.size();
    int left = 0, right = n - 1;
    while(left < right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] > nums[n - 1])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }

    return nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.0〜n-1 中缺失的数字

1.题目链接

• 0〜n-1 中缺失的数字

2.算法原理详解

• 本题的二段性算是比较逆天的，可以借此拓展对二段性的理解
• 在这个升序的数组中：
  • 在第⼀个缺失位置的左边，数组内的元素都是与数组的下标相等的
  • 在第⼀个缺失位置的右边，数组内的元素与数组下标是不相等的
• 因此，可以利⽤这个**「⼆段性」，来使⽤「⼆分查找」**算法
  

3.代码实现

int takeAttendance(vector<int>& records) 
{
    int left = 0, right = records.size() - 1;
    while(left < right)
    {
        int mid = left + (right - left) / 2;
        if(mid == records[mid])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }

    return left == records[left] ? (left + 1) : left; // 处理边界情况
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18