有二断性

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

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

二分

两次二分，第一次找到左边起始位置，第二次找右边位置

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0;
        int r = n - 1;
        while(l <= r){
            int mid = l + r >> 1;
            if(nums[mid] < target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        if(l == n || nums[l] != target){
            return {-1, -1};
        }
        r = n - 1;
        vector<int> ans;
        ans.push_back(l);
        while(l <= r){
            int mid = l + r >> 1;
            if(nums[mid] == target){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        ans.push_back(r);
        return ans;

    }
};
162、寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

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
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if(n == 1 || nums[0] > nums[1]){
            return 0;
        }
        if(nums[n - 1] > nums[n - 2]){
            return n - 1;
        }
        
        int l = 0;
        int r = n - 1;
        while(l <= r){
            int mid = l + r >> 1;
            cout << mid << endl;
            if(nums[mid] > nums[mid + 1]){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
            cout << l << " " << r << endl;
        }
        return l;
    }

};
153、寻找旋转排序数组中的最小值

已知一个长度为 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = -1;
        int r = nums.size() - 1;
        while(l + 1 < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[n - 1]){
                r = mid;
            }else{
                l = 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 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

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
class Solution {
public:

    bool is_blue(int mid, int target, int end){
        if(mid > end){
            return target <= mid && target > end;
        }else{
            return target <= mid || target > end;
        }
    }
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int l = -1;
        int r = nums.size();
        while(l + 1 < r){
            int mid = l + r >> 1;
            if(is_blue(nums[mid], target, nums[n - 1])){
                r = mid;
            }else{
                l = mid;
            }
        }
        if(target == nums[r])
            return r;
        else{
            return -1;
        }
    }
};