Algorithms: Search
Published:
查找的题目基本是二分查找，排序一般是快排或归并
快排是left = 0, right = x.size() - 1; while(low <= high); high = mid - 1; low = mid + 1;
结果是
- target存在在数组中，返回该target所在位置
- 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
- 在某个位置进行了旋转，依然可以使用二分查找，但是比较难想。
- mid在旋转点的左边
此时考虑target在low和mid之间的情况， high = mid - 1。其他情况low = mid + 1。 - 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;
}