通用模板

image-20220515220512986

注意【没有蓝色区域】和【没有红色区域】的细节如何处理， 比如查找第一个大于等于5的元素，如果数组中所有元素都小于5那么，返回的r 直接访问会越界，需要特殊处理一下， 同理 返回 L 的时候如果是-1，也需要特殊处理才行

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

1
2
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

1
2
输入: nums = [1,3,5,6], target = 2
输出: 1
1
2
3
4
5
6
7
8
9
int searchInsert(vector<int>& nums, int target) {
    int l = -1,r = nums.size();
    while(l+1 != r){
        int mid = l + (r-l)/2;
        if(nums[mid] >= target)r = mid;
        else if(nums[mid] < target)l = mid; 
    }
    return r;
}

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

1
2
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> searchRange(vector<int>& nums, int target) {
    int l = -1,r = nums.size();
    vector<int>result(2,0);
    
    //left_bound
    while(l+1 != r){
        int mid = (l+r)/2;
        if(nums[mid] >= target)r = mid;
        else l = mid;
    }
    if(r == nums.size() || nums[r] != target)result[0] = -1;
    else result[0] = r;
    
    //right_bound
    l = -1;r = nums.size();
    while(l+1 != r){
        int mid = (l+r)/2;
        if(nums[mid] > target)r = mid;
        else l = mid;
    }
    if(l == -1 || nums[l] != target)result[1] = -1;
    else result[1] = l;
    return result;
}

69. x 的平方根

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

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

1
2
3
4
5
6
7
8
9
int mySqrt(int x) {
    long long l = 0,r = x + 1;
    while(l+1 != r){
        long long mid = (l+r)/2;
        if(mid*mid <= x)l = mid;
        else r = mid;
    }
    return l;
}

367. 判断是否为有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

1
2
3
4
5
6
7
8
9
bool isPerfectSquare(int num) {
    long long l = -1,r = (long long)num + 1;
    while(l+1 != r){
        long long mid = (l + r)/2;
        if(mid * mid >= num)r = mid;
        else l = mid;
    }
    return r*r == num;
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

1
2
3
4
5
6
7
8
9
int missingNumber(vector<int>& nums) {
    int l = -1,r = nums.size();
    while(l+1 != r){
        int mid = (l+r)/2;
        if(nums[mid] == mid)l=mid;
        else r = mid;
    }
    return r;
}

剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

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

示例 1：

1
2
输入：numbers = [3,4,5,1,2]
输出：1

示例 2：

1
2
输入：numbers = [2,2,2,0,1]
输出：0

这道题稍微复杂点，原因可能出现[1,1,1,0,1]或[1,0,1,1,1]这就需要开始做个判断，把后面的相同的1给移掉

蓝色区域：大于nums[end]

红色区域：小于等于nums[end]

最终返回必定是r，因为红色区域都是小于等于nums[end]，那么红色区域最左边必然是最小值

1
2
3
4
5
6
7
8
9
10
11
int minArray(vector<int>& nums) {
    int end = nums.size() - 1;
    while(end > 0 && nums[end] == nums[0])end--;
    int l = -1, r = end + 1;
    while(l + 1 != r){
        int mid = l + (r-l)/2;
        if(nums[mid] > nums[end])l = mid;
        else if(nums[mid] <= nums[end])r = mid;
    }
    return nums[r];
}

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

1
2
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1
  1. 先旋转数组的最小值，即那个旋转点
  2. 然后根据nums[end]和target比较判断是在前半部分还是后半部分，并且最好不要用nums[0]和target做比较，因为数组可能在0处旋转，即相当于未旋转，比较难以判断边界
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
int findMin(vector<int>& nums) {
    int end = nums.size() - 1;
    while(end >= 0 && nums[end] == nums[0])end--;
    int l = -1, r = end + 1;
    while(l + 1 != r){
        int mid = l + (r-l)/2;
        if(nums[mid] > nums[end])l = mid;
        else if(nums[mid] <= nums[end])r = mid;
    }
    return r;
}
int search(vector<int>& nums, int target) {
    int m = findMin(nums);
    int l=-1,r=nums.size();

    if(target > nums[end])r = m;//大于nums[end]说明必定在前半段
    else l = m - 1;             //否则在mid~end的后半段

    while(l + 1 != r){
        int mid = l + (r-l)/2;
        if(nums[mid] == target)return mid;
        else if(nums[mid] > target)r = mid;
        else l = mid;
    }
    return -1;
}

81. 搜索旋转排序数组 II

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
int findMin(vector<int>& nums,int &end) {
    end = nums.size() - 1;
    while(end > 0 && nums[end] == nums[0])end--;
    int l = -1, r = end + 1;
    while(l + 1 != r){
        int mid = l + (r-l)/2;
        if(nums[mid] > nums[end])l = mid;
        else if(nums[mid] <= nums[end])r = mid;
    }
    return r;
}
bool search(vector<int>& nums, int target) {
    int end;
    int m = findMin(nums,end);
    int l=-1,r=end+1;

    if(target > nums[end])r = m;//大于nums[end]说明必定在前半段
    else l = m - 1;             //否则在mid~end的后半段

    while(l + 1 != r){
        int mid = l + (r-l)/2;
        if(nums[mid] == target)return true;
        else if(nums[mid] > target)r = mid;
        else l = mid;
    }
    return false;
}