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

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

該套路的結果是

1. target存在在數(shù)組中，返回該target所在位置

2. target不在數(shù)組中，low = high + 1，target應該在low和high所在元素的中間

74. Search a 2D Matrix

基本的二分查找題目，是個拍好序的矩陣。需要注意的地方是low、high的取值，while循環(huán)條件，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

查找數(shù)值數(shù)組中目標數(shù)值應該插入的位置

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;

循環(huán)條件為low < high。因為等于的情況會觸發(fā)判別條件中的一種。

返回值為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;
}