一：搜索二维矩阵

image-20251014102722721

1. 两次查找

第一次在每行的第一个元素查找，然后在该行中查找

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        auto row = upper_bound(matrix.begin(), matrix.end(), target, [](int target, vector<int>& row){return target < row[0];});  // 需要自定义比较函数，因为一个值无法与数组比较
        if (row == matrix.begin()) return false;
        --row;
        return binary_search(row->begin(), row->end(), target);
    }
};

image-20251014151844871

2. 一次查找

将二位矩阵展开为一维，然后把索引转换为二维去处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = matrix.size();
        int col = matrix[0].size();
        int left = 0, right = row * col - 1;
        while (left <= right)
        {
            int mid = ((right - left) >> 1) + left;
            int cur = matrix[mid / col][mid % col];     // 对列处理
            if (cur > target) right = mid - 1;
            else if (cur < target) left = mid + 1;
            else return true;
        }
        return false;
    }
};

image-20251014151852230

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

image-20251014153450858

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
25
26
27
28
29
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = BinarySearch(nums, target, true);
        int right = BinarySearch(nums, target, false) - 1;
        if (left >= 0 && left <= right && right < nums.size() && nums[left] == target && nums[right] == target)
            return vector<int>{left, right};
        return vector<int>{-1, -1};
    }
    int BinarySearch(vector<int>& nums, int target, int lowFlag)
    {
        int left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        int ans = nums.size();
        while (left <= right)
        {
            mid = (right - left) / 2 + left;
            if (nums[mid] > target || (nums[mid] >= target && lowFlag))
            {
                right = mid - 1;
                ans = mid;
            }
            else
                left = mid + 1;
        }
        return ans;
    }
};

image-20251014153545413

三：搜索旋转排序数组

image-20251015094326876

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
25
26
27
28
29
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        if (len == 0) return false;
        if (len == 1) return target == nums[0] ? 0 : -1;
        int left = 0, right = len - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = (right - left) / 2 + left;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid])
            {
                if (nums[0] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            } else
            {
                if (nums[mid] < target && target <= nums[len - 1])
                    left = mid + 1;
                else   
                    right = right -1;
            }
        }
        return -1;
    }
};

image-20251015094352523

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

image-20251015102201606

1. 二分查找

这题和上题类似，主要利用划分后最小值可能存在的位置，左边或者右边

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 left = 0;
        int right = nums.size() - 1;
        int mid = 0;
        while (left < right)
        {
            mid = (right - left) / 2 + left;
            if (nums[mid] < nums[right])
                right = mid;
            else
                left = mid + 1;
        }
        return nums[left];
    }
};

image-20251015102223895

五：最小栈

image-20251015103619524

1. 辅助栈

栈的实现可以直接使用stack，但这里需要记录最小值，并且常数查找，因此使用辅助栈来记录每一个元素对应的最小值

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
class MinStack {
    stack<int> value;
    stack<int> min;
public:
    MinStack() {
        min.push(INT_MAX);
    }
    
    void push(int val) {
        value.push(val);
        min.push(std::min(val, min.top()));
    }
    
    void pop() {
        value.pop();
        min.pop();
    }
    
    int top() {
        return value.top();
    }
    
    int getMin() {
        return min.top();
    }
};

image-20251015103829912