【C++刷题】优选算法——二分

1. 二分查找

// 朴素的二分模板
int search(vector<int>& nums, int target)
{
    int left = 0, right = nums.size() - 1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] > target)
        {
            right = mid - 1;
        }
        else if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }  
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

vector<int> searchRange(vector<int>& nums, int target)
{
    vector<int> v = {-1, -1};
    if(nums.size() < 1) return v;
    int left = 0, right = nums.size() - 1;
    // 二分左端点 - 查找左边界的二分模板
    while(left < right) // 循环条件
    {
        int mid = left + (right - left) / 2; // 求中点的方式
        if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    if(nums[left] == target) v[0] = left;
    else return v;

    // left = 0, right = nums.size() - 1;
    right = nums.size() - 1;
    // 二分右端点 - 查找右边界的二分模板
    while(left < right) // 循环条件
    {
        int mid = left + (right - left + 1) / 2; // 求中点的方式
        if(nums[mid] > target)
        {
            right = mid - 1;
        }
        else
        {
            left = mid;
        }
    }
    v[1] = right;
    return v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

3. x 的平方根

int mySqrt(int x)
{
    size_t left = 0, right = x;
    while(left < right)
    {
        long long mid = left + (right - left + 1) / 2;
        if(mid * mid > x)
        {
            right = mid - 1;
        }
        else
        {
            left = mid;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. 搜索插入位置

int searchInsert(vector<int>& nums, int target) 
{
    int left = 0, right = nums.size() - 1;
    while(left < right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    if(target > nums[left]) return left + 1;
    else return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5. 山脉数组的峰顶索引

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 - 1] < arr[mid])
        {
            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

6. 寻找峰值

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])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

// 以nums[nums.size() - 1]为参考
int findMin(vector<int>& nums)
{
    int left = 0, right = nums.size() - 1;
    while(left < right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] > nums[nums.size() - 1])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return nums[left];
}
// 以nums[0]为参考
int findMin(vector<int>& nums)
{
    int left = 0, right = nums.size() - 1;
    while(left < right)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] >= nums[0])
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return nums[left] > nums[0] ? nums[0] : nums[left];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

8. 点名

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])
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return left != records[left] ? left : left + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17