10. 查找

---

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

快排套路是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;
}

---