35. 搜索插入位置✅

二分模板题

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1, mid;
        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        if(nums[mid] < target) return mid + 1;
        return mid;
    }
};

---

74. 搜索二维矩阵✅

以空间换脑细胞，直接把矩阵的元素存入新数组，再二分

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        vector<int> nums;
        for(auto &v : matrix) {
            for(auto &num : v) {
                nums.push_back(num);
            }
        }

        int left = 0, right = nums.size() - 1, mid;
        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) {
                return true;
            } else if(nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
};

---

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

如果找到目标值，向两边扩散找到边界即可

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return {-1, -1}; 

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

        if(nums[mid] != target) {
            return {-1, -1};
        } else {
            int lb, rb; //left&right border
            if(!mid) lb = mid;
            else {
                for(int i = mid; i >= 0; i--) {
                    if(nums[i] != target) {
                        lb = i + 1;
                        break;
                    }
                }
            }

            if(mid == nums.size() - 1) rb = nums.size() - 1;
            else {
                for(int i = mid; i < nums.size(); i++) {
                    if(nums[i] != target) {
                        rb = i - 1;
                        break;
                    }
                }
            }
            return {lb, rb};
        }
    }
};

---

33. 搜索旋转排序数组✅

两段分开二分即可

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int border = 0; //前半部分有border个元素
        bool isReverse = false;
        for(int i = 1; i < nums.size(); i++) {
            border = i; 
            if(nums[i] < nums[i-1]) {
                isReverse = true;
                break;
            }
        }
        if(!isReverse) border = nums.size();
        // cout << "border:" << border << endl;
        int left, right, mid;
        if(target >= nums[0]) { //目标值要在前半部分找
            left = 0;
            right = border - 1;
            while(left <= right) {
                mid = (left + right) / 2;
                if(nums[mid] == target) {
                    return mid;
                } else if(nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        } else {
            left = border;
            right = nums.size() - 1;
            while(left <= right) {
                mid = (left + right) / 2;
                if(nums[mid] == target) {
                    return mid;
                } else if(nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

---

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

也没用到二分啊 遍历一下即可

class Solution {
public:
    int findMin(vector<int>& nums) {
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] < nums[i-1]) return nums[i];
        }
        return nums[0];
    }
};

---

4. 寻找两个正序数组的中位数✅

以空间换脑细胞 直接塞进一个数组 排序后取中间值

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums;
        for(auto &num : nums1) nums.push_back(num);
        for(auto &num : nums2) nums.push_back(num);
        ranges::sort(nums);
        
        if(nums.size() % 2) {
            return nums[nums.size() / 2];
        } else {
            return (nums[nums.size() / 2] + nums[nums.size() / 2 - 1]) / 2.0;
        }
    }
};