Algorithms: Search

2 minute read

Published:

查找的题目基本是二分查找,排序一般是快排或归并

快排是left = 0, right = x.size() - 1; while(low <= high); high = mid - 1; low = mid + 1;

结果是

  1. target存在在数组中,返回该target所在位置
  2. target不在数组中,low = high + 1,target应该在low和high所在元素的中间

74. Search a 2D Matrix

  • 基本的二分查找题目,是个拍好序的矩阵。需要注意的地方是low、high的取值,while循环条件,low、high更新
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = m ? matrix[0].size() : 0;
    if (!m || !n) return false;
    int high = m*n - 1, low = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (matrix[mid/n][mid%n] > target) high = mid - 1;
        else if(matrix[mid/n][mid%n] < target) low = mid + 1;
        else return true;
    }
    return false;
}

35. Search Insert Position

  • 查找数值数组中目标数值应该插入的位置
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        while (low <= high) {
            int mid = (low + high)/2;
            if (nums[mid] > target) high = mid - 1;
            else if(nums[mid] < target) {
                low = mid + 1;
            } else {
                return mid;
            }
        }

        return low;
    }
}

33. Search in Rotated Sorted Array

  • 在某个位置进行了旋转,依然可以使用二分查找,但是比较难想。
  1. mid在旋转点的左边
    此时考虑target在low和mid之间的情况, high = mid - 1。其他情况low = mid + 1。
  2. mid在旋转点的右边
    此时考虑target在mid和high之间的情况,low = mid + 1。其他情况high = mid - 1;
  • 循环条件为low < high。因为等于的情况会触发判别条件中的一种。
  • 返回值为nums[low]
int search(vector<int>& nums, int target) {
    int m = nums.size();
    if (!m) return -1;

    int low = 0, high = m - 1;
    while (low < high) {
        int mid = (low + high)/2;
        if (nums[mid] == target) return mid;
        if (nums[low] <= nums[mid]) {
            if (target >= nums[low] && target < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {
            if (target > nums[mid] && target <= nums[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return nums[low] == target ? low : -1;
}

81. Search in Rotated Sorted Array II

  • 与上题类似,额外去除了nums[low] == nums[mid] == nums[high]的情况
bool search(vector<int>& nums, int target) {
    if (nums.empty()) return false;

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