LeetCode 每周算法 7（二分查找）

LeetCode 每周算法 7（二分查找）

二分查找算法：

class Solution {  
public:  // 定义一个函数，接收一个整数向量nums和一个整数target，返回目标值在数组中的插入位置  int searchInsert(vector<int>& nums, int target) {  int left = 0, right = nums.size() - 1; // 定义二分查找的左右边界// 当左边界小于等于右边界时，执行循环  while (left <= right) {  // 计算中间位置（注意：这里使用的是整数除法，结果向下取整）  int mid = (left + right) / 2;  // 如果中间位置的元素小于目标值，说明目标值在右半部分或就是右边界的值  if (nums[mid] < target) {  left = mid + 1; // 更新左边界为中间位置的下一个位置  } else {  // 如果中间位置的元素大于等于目标值，说明目标值在左半部分或就是当前中间位置的值  // 注意：这里用right = mid - 1是为了确保如果target是nums中的一个元素时，能返回它的正确索引  // 如果是要找插入位置，且target不在nums中，则应该直接返回left（因为此时left指向了第一个大于target的位置）  right = mid - 1; // 更新右边界为中间位置的前一个位置  }  }  // 当循环结束时，left将指向第一个大于target的位置（如果target不在nums中）  // 或者指向target在nums中的位置（如果target在nums中，并且前面有与其相等的元素）  // 由于题目要求返回插入位置，且数组已排序，因此直接返回left即可  return left;  }  
};

class Solution {  
public:  // 定义一个函数，接收一个二维整数向量matrix和一个整数target，返回是否在matrix中找到target  bool searchMatrix(vector<vector<int>>& matrix, int target) {  int m = matrix.size();       // 获取矩阵的行数  int n = matrix[0].size();    // 获取矩阵的列数（假设所有行长度相同）  int left = 0, right = m * n - 1; // 初始化二分查找的上下界，将整个矩阵视为一个一维数组进行查找  // 当left小于等于right时，执行循环  while (left <= right) {  // 计算中间位置（注意这里使用(right - left) / 2 + left来避免直接(left + right) / 2可能导致的溢出）  int mid = (left + right) / 2;  // 将一维的mid索引转换回二维的(x, y)索引  int x = mid / n;         // x是行索引  int y = mid % n;         // y是列索引   // 根据中间位置的值与目标值的比较结果，调整二分查找的上下界  if (matrix[x][y] < target) {  left = mid + 1; // 如果中间值小于目标值，则目标值在右半部分  } else if (matrix[x][y] > target) {  right = mid - 1; // 如果中间值大于目标值，则目标值在左半部分  } else {  return true; // 如果中间值等于目标值，则找到目标，返回true  }  }  // 如果循环结束还没有找到目标值，则返回false  return false;  }  
};

class Solution {  
public:  // 辅助函数：使用二分查找找到第一个大于或等于target//（当lower为true时）或第一个大于target（当lower为false时）的元素的索引  int binarySearch(vector<int>& nums, int target, bool lower) {  int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size(); // 初始化左右边界和答案变量  while (left <= right) { // 当左边界小于等于右边界时继续搜索  int mid = (left + right) / 2; // 计算中间位置  if (nums[mid] > target || (lower && nums[mid] == target)) {  // 如果当前中间元素大于target，或者（lower为true且中间元素大于等于target）  // 则调整右边界，并将ans更新为mid（因为我们要找的是第一个满足条件的元素）  right = mid - 1;  ans = mid;  } else {  // 否则，继续向右搜索  left = mid + 1;  }  }  // 循环结束时，ans中存储的是第一个满足条件的元素的索引，或者如果都不满足，则为nums.size()  return ans;  }  // 主函数：查找target在nums中的范围（起始和结束索引），如果不存在则返回{-1, -1}  vector<int> searchRange(vector<int>& nums, int target) {  // 首先，通过binarySearch找到第一个大于等于target的元素的索引  int leftIdx = binarySearch(nums, target, true);  // 然后，通过binarySearch找到第一个大于target的元素的索引，并减1得到最后一个等于target的元素的索引  int rightIdx = binarySearch(nums, target, false) - 1;  // 检查找到的左右索引是否有效（即存在且target确实存在于该范围内）  if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {  // 如果有效，则返回这个范围  return vector<int>{leftIdx, rightIdx};  }  // 否则，返回{-1, -1}表示未找到  return vector<int>{-1, -1};  }  
};

class Solution {  
public:  int search(vector<int>& nums, int target) {  int n = (int)nums.size(); // 获取数组nums的长度  if (!n) { return -1; } // 如果数组为空，则直接返回-1，表示未找到目标值  if (n == 1) { return nums[0] == target ? 0 : -1; } // 如果数组只有一个元素，则判断该元素是否为目标值，并返回相应结果  int l = 0, r = n - 1; // 初始化左右指针，分别指向数组的首尾  while (l <= r) { // 当左指针小于等于右指针时，进行循环  int mid = (l + r) / 2; // 计算中间位置索引  if (nums[mid] == target) return mid; // 如果中间位置的值等于目标值，则返回该位置索引  // 以下处理旋转数组的情况  if (nums[0] <= nums[mid]) { // 如果左半部分（包括mid）是有序的  if (nums[0] <= target && target < nums[mid]) { // 如果目标值在左半部分内  r = mid - 1; // 调整右指针，继续在左半部分搜索  } else {  l = mid + 1; // 否则，目标值在右半部分，调整左指针  }  } else { // 如果右半部分（不包括mid，但包括nums[0]）是有序的  if (nums[mid] < target && target <= nums[n - 1]) { // 如果目标值在右半部分内  l = mid + 1; // 调整左指针，继续在右半部分搜索  } else {  r = mid - 1; // 否则，目标值在左半部分，调整右指针  }  }  }  return -1; // 如果循环结束仍未找到目标值，则返回-1  }  
};

class Solution {  
public:  int findMin(vector<int>& nums) {  // 定义左右指针，初始时分别指向数组的第一个和最后一个元素  int left = 0;  int right = nums.size() - 1;  // 当左指针小于右指针时，进行循环，确保能找到最小值  while (left < right) {  // 防止溢出，计算中点时使用 left + (right - left) / 2  int mid = left + (right - left) / 2;  // 如果中点元素小于右指针指向的元素，说明最小值在中点左侧（包括中点）  // 因为右半部分（mid+1到right）是有序的，且都大于nums[mid]  if (nums[mid] < nums[right]) {  right = mid;  }  // 如果中点元素大于等于右指针指向的元素，说明最小值在中点右侧  // 因为左半部分（left到mid）是无序的，但nums[mid]一定大于nums[left]，  // 所以最小值不可能在左半部分，只能在中点右侧  else {  left = mid + 1;  }  }  // 当left == right时，循环结束，此时left（或right）指向的就是最小值的位置  // 返回该位置上的元素即为所求的最小值  return nums[left];  }  
};

class Solution {  
public:  // 查找两个有序数组中第k小的元素  int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {  int m = nums1.size(); // 数组nums1的长度  int n = nums2.size(); // 数组nums2的长度  int index1 = 0, index2 = 0; // 两个数组的起始索引  while (true) {  // 如果nums1已经遍历完，那么第k小的元素一定在nums2中  if (index1 == m) {  return nums2[index2 + k - 1];  }  // 如果nums2已经遍历完，那么第k小的元素一定在nums1中  if (index2 == n) {  return nums1[index1 + k - 1];  }  // 如果k为1，那么当前两个指针指向的元素中较小的那个就是第k小的元素  if (k == 1) {  return min(nums1[index1], nums2[index2]);  }  // 在两个数组中分别找到第k/2小的元素的索引，但不超过数组长度  int newIndex1 = min(index1 + k / 2 - 1, m - 1);  int newIndex2 = min(index2 + k / 2 - 1, n - 1);  int pivot1 = nums1[newIndex1]; // nums1中的第k/2小的元素  int pivot2 = nums2[newIndex2]; // nums2中的第k/2小的元素  // 根据pivot1和pivot2的大小关系，决定排除哪一部分的元素  if (pivot1 <= pivot2) {  // 如果nums1的第k/2小的元素小于等于nums2的第k/2小的元素  // 那么nums1中前newIndex1+1个元素都不可能是第k小的元素  k -= newIndex1 - index1 + 1;  index1 = newIndex1 + 1;  } else {  // 如果nums1的第k/2小的元素大于nums2的第k/2小的元素  // 那么nums2中前newIndex2+1个元素都不可能是第k小的元素  k -= newIndex2 - index2 + 1;  index2 = newIndex2 + 1;  }  }  }  // 查找两个有序数组的中位数  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {  int totalLength = nums1.size() + nums2.size(); // 两个数组的总长度  if (totalLength % 2 == 1) {  // 如果总长度为奇数，则中位数为第(totalLength+1)/2小的元素  return getKthElement(nums1, nums2, (totalLength + 1) / 2);  } else {  // 如果总长度为偶数，则中位数为第(totalLength/2)小和第(totalLength/2+1)小元素的平均值  return (getKthElement(nums1, nums2, (totalLength + 1) / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;  }  }  
};