LeetCode.34.33.74(二分查找)

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

class Solution {
  public:
    vector<int> searchRange(vector<int> &nums, int target) {
        int start = 0, end = nums.size() - 1;
        while (end >= start) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > target)
                end = mid - 1;
            else if (nums[mid] < target)
                start = mid + 1;
            else {
                if (nums[start] < target) {
                    if (nums[(start + mid) / 2] < target) {
                        start = (start + mid) / 2 + 1;
                    } else
                        start += 1; //这里会塌掉
                }
                if (nums[end] > target) {
                    if (nums[(end + mid) / 2] < target) {
                        end = (end + mid) / 2 - 1;
                    } else
                        end -= 1; //这里会塌掉
                }
                if (nums[start] == target && nums[end] == target)
                    return {start, end};
            }
        }
        return {-1, -1};
        // 88/88 cases passed (4 ms)
        // Your runtime beats 94.49 % of cpp submissions
        // Your memory usage beats 54.03 % of cpp submissions (13.3 MB)
        //在重复区间非常长的极端情况下时间复杂度感觉会塌到O(n)，还是左右界线都找一遍是最安全的
    }
};

33.搜索旋转排序数组

class Solution {
  public:
    /*int search(vector<int> &nums, int target) {
        int m = nums.size();
        int left = searchK(nums), right = left + m - 1;
        while (right >= left) {
            int mid = left + (right - left) / 2;
            if (nums[mid % m] > target)
                right = mid - 1;
            else if (nums[mid % m] < target)
                left = mid + 1;
            else
                return mid % m;
        }
        return -1;
    }
    int searchK(vector<int> &nums) {
        int start = 0, end = nums.size() - 1;
        while (end >= start) {
            int mid = start + (end - start) / 2;
            if (nums[mid] < nums[start])
                end = mid;
            else if (nums[mid] > nums[end])
                start = mid + 1;
            else
                return start;
        }
        return -1;
    }*/
    // 195/195 cases passed (4 ms)
    // Your runtime beats 70.9 % of cpp submissions
    // Your memory usage beats 93.33 % of cpp submissions (10.7 MB)
    //萌新算法==
    int search(vector<int> &nums, int target) { return searchB(nums, target, 0, nums.size() - 1); }
    int searchB(vector<int> &nums, int target, int start, int end) {
        if (start > end)
            return -1;
        int mid = start + (end - start) / 2;
        if (nums[mid] >= nums[start]) //断点在右
        {
            if (target >= nums[start] && target <= nums[mid]) {
                return bsearchWithoutRecursion(nums, start, mid, target);
            } else {
                return searchB(nums, target, mid + 1, end);
            }
        } else if (nums[mid] < nums[start]) //断点在左
        {
            if (target >= nums[mid] && target <= nums[end]) {
                return bsearchWithoutRecursion(nums, mid, end, target);
            } else {
                return searchB(nums, target, start, mid - 1);
            }
        }
        return nums[mid] == target ? mid : -1;
    }
    int bsearchWithoutRecursion(vector<int> &nums, int low, int high, int target) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > target)
                high = mid - 1;
            else if (nums[mid] < target)
                low = mid + 1;
            else
                return mid;
        }
        return -1;
    }
    // 195/195 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 65.05 % of cpp submissions (10.8 MB)
};

74.搜索二维矩阵

class Solution {
  public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        /*int line = -1;
        int left = 0, right = matrix.size() - 1;
        while (right >= left) {
            int middle = left + (right - left) / 2;
            if (matrix[middle][0] > target)
                right = middle - 1;
            else if (matrix[middle][0] < target)
                left = middle + 1;
            else {
                line = middle;
                break;
            }
        }
        line = line == -1 ? left - 1 : line;
        if (line == -1)
            return false;
        left = 0;
        right = matrix[line].size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (matrix[line][mid] > target)
                right = mid - 1;
            else if (matrix[line][mid] < target)
                left = mid + 1;
            else
                return true;
        }
        return false;*/
        // 133/133 cases passed (4 ms)
        // Your runtime beats 77.32 % of cpp submissions
        // Your memory usage beats 42.21 % of cpp submissions (9.3 MB)
        if (matrix.empty() || matrix[0].empty())
            return 0;
        //从左下角上右上角寻找目标值
        int x = matrix.size() - 1, y = 0;
        while (x >= 0 && y < matrix[0].size()) {
            if (matrix[x][y] > target)
                x--; //[x,y]的值比目标值大，上移
            else if (matrix[x][y] < target)
                y++; //[x,y]的值比目标值小，右移
            else
                return true;
        }
        return false;
        // 133/133 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 90.86 % of cpp submissions (9.1 MB)
        //这种方法居然更快我不能接受，被计划里的“二分查找”给欺骗了呀
    }
};