LEETCODE HOT 100 二分查找 C‘s Log

二分查找也是最重要的就是明确自己变换的前提也就是到底是哪个闭哪个开转化成下面这句话可以这么思考关键不在于区间里的元素具有什么性质而是区间外面的元素具有什么性质这个也是我在刷B站的灵神课的时候无意间看到的热一35. 搜索插入位置 - 力扣LeetCode这道题就是对区间到底开不开以及对应的大小符号的一个判断这里我们按照上面的逻辑和左闭右开区间来看1.区间有效进入中点和左右指针的挪动区间有效的意思是这个区间存在左闭右开那么左必须小于右这个区间才成立2.移动中点也就是中点不在区间内但是需要作为区间的最边边上的位置移动左区间的时候这个左指针是中点加一移动右指针这里中点本身就不包含在区间内可以直接等于右跳出循环的时候就是左区间和右区间相遇了【这里不可能存在左区间到右区间的右边去的情况结合上一轮循环进行判断】那么此时返回的就是左指针【右指针也可以】class Solution { int lower_bound2(vectorint nums, int target) { int left 0, right nums.size(); // 左闭右开区间 [left, right) // 区间不为空 while (left right) { // nums[left-1] target // nums[right] target int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; } public: int searchInsert(vectorint nums, int target) { return lower_bound2(nums, target); } };在针对左闭右闭区间的这里为什么不能返回right而必须返回left返回left因为left是“追赶者”它一直试图往右找更大的直到越过边界。不返回right因为right是“排斥者”它一直在把不符合条件 target的数排除在左边。循环结束时它正好停在“最后一个不符合条件的数”上class Solution { int lower_bound(vectorint nums, int target) { int left 0, right (int) nums.size() - 1; // 闭区间 [left, right] while (left right) { // 区间不为空 // nums[left-1] target // nums[right1] target int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; } public: int searchInsert(vectorint nums, int target) { return lower_bound(nums, target); } };74. 搜索二维矩阵 - 力扣LeetCode矩阵的每一行是递增的且每行的第一个数大于前一行的最后一个数如果把矩阵每一行拼在一起我们可以得到一个递增数组【闭区间写法】class Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { int m matrix.size(), n matrix[0].size(); int left 0, right m * n - 1; // left right区间有效 while (left right) { int mid left (right - left) / 2; // 将一维坐标映射回二维坐标 // 假设 n 是列数 int x matrix[mid / n][mid % n]; if (x target) { return true; // 找到目标值 } else if (x target) { left mid 1; } else { right mid - 1; } } return false; } };34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode“非递减顺序排列”的意思是后面的数要么比前面的大要么和前面的相等依旧左闭右闭class Solution { // lower_bound 返回最小的满足 nums[i] target 的下标 i // 如果数组为空或者所有数都 target则返回 nums.size() // 要求 nums 是非递减的即 nums[i] nums[i 1] int lower_bound(vectorint nums, int target) { int left 0, right (int) nums.size() - 1; // 闭区间 while (left right) { // 不为空 // nums[left-1] target // nums[right1] target int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; left mid 1; } } // left right1 // nums[left-1] target 而 nums[left] nums[right1] target // left 就是第一个 target 的元素下标 return left; } public: vectorint searchRange(vectorint nums, int target) { int start lower_bound(nums, target); if (start nums.size() || nums[start] ! target) { return {-1, -1}; //没有 target } int end lower_bound(nums, target 1) - 1; return {start, end}; } };33. 搜索旋转排序数组 - 力扣LeetCode这道题的逻辑就是下面一道题加上在有序数组中找到目标值两个结合起来的逻辑重点是判断各种返回的值也就是具体什么时候反馈什么样的值来确定目标这里每个值都独一无二也就是说不存在重复的值为什么返回left 还是上面最粗的字表述的left和right在左闭右闭的关系class Solution { int findMinIndex(vectorint nums) { int left 0; int right nums.size() - 1; // 区间不为空也就是等到leftright时这个值就是最小值 while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) { // 中间 右边 // 说明 mid 还在“大数段”最小点点一定在 mid 的右侧 left mid 1; } else { // 中间 右边 // 说明 [mid, right] 这一段是有序的 // 断点可能是 mid也可能在 mid 左侧 right mid; } } return left; // 此时 left right } int lower_bound(vectorint nums, int left, int right, int target) { while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; // 范围缩小到 [left, mid-1] } else { left mid 1; // 范围缩小到 [mid1, right] } } // 循环结束时 left right 1 // left 指向的是第一个 target 的位置 return left nums.size() nums[left] target ? left : -1; } public: int search(vectorint nums, int target) { int i findMinIndex(nums); // i 是最小值的下标 if (target nums.back()) { // 目标值比数组的最后一个值大说明在前半段数组更大 // i0说明更大的段没了 if (i 0) return -1; return lower_bound(nums, 0, i - 1, target); } else { //target 在第二段 [i, n-1] return lower_bound(nums, i, nums.size() - 1, target); } } };153. 寻找旋转排序数组中的最小值 - 力扣LeetCode这个旋转几次应该无所谓的反正最后得到一个一段加一段有顺序的数组进行判断就可以了通过mid与左右点的大小判断来判断最小值可能出现在当前数组的左半段还是右半段class Solution { public: int findMin(vectorint nums) { int left 0; int right nums.size()-1; while (leftright){ int mid left (right-left)/2; if(nums[mid]nums[right]){ // mid 在左半段最小值在右边 left mid 1; } else{ // mid 在右半段最小值是 mid 或者在左边 right mid; // mid本身有可能就是答案 } } // 结束时 left right return nums[left]; } };4. 寻找两个正序数组的中位数 - 力扣LeetCodeleft 和 right 是在数组 a 上不断收缩的搜索边界用来锁定最佳切点 i而 i 和 j 则是最终落在两个数组上的分割刻度用来划定左右阵营并确定中位数的位置没有好的办法只能自己用手画去理解为什么是a[i-1]左半边的最大值这i个元素的下标分别是0, 1, ..., i-1那么这堆元素里最后一个最大的那个自然就是下标为i-1的元素。同理a右边的最小值即第i1个元素其下标就是i即a[i]“闭区间”体现在while (left right)和right m上。这意味着我们的切割线i可以取到边界值i可以是 0表示a一个元素都不贡献给左边。此时a[i-1]即a[-1]这就是为什么要用INT_MIN来保护的原因。i可以是 m表示a把所有元素都贡献给左边。此时a[i]即a[m]这就是为什么要用INT_MAX来保护的原因。总体来说就是按照灵神的思路上面当作数组a,下面当作数组b不断地去改变二分的结构class Solution { public: double findMedianSortedArrays(vectorint a, vectorint b) { // a 是较短的数组 if (a.size() b.size()) { swap(a, b); } int m a.size(), n b.size(); int left 0; int right m; // i 可以取到 m int totalLeft (m n 1) / 2; // 左半边总共需要的元素个数 while (left right) { //不为空 int i left (right - left) / 2; // a 数组左边有 i 个元素 int j totalLeft - i; // b 数组左边有 j 个元素ij总长度平均分的一半 // 边界保护防止 i0 或 jn 时越界 int aLeftMax (i 0) ? INT_MIN : a[i - 1]; int bRightMin (j n) ? INT_MAX : b[j]; // a[i-1] 是 a 左边的最大值b[j] 是 b 右边的最小值 // 如果 a 左边的最大值 b 右边的最小值说明 a 分给左边的太多了 if (aLeftMax bRightMin) { right i - 1; // i 太大了往左找 } // 如果 a 左边的最大值 b 右边的最小值说明 i 合法或者还可以更大往右找更大的 i else if (aLeftMax bRightMin) { left i 1; } } // 循环结束时left right // right 是最终的切割位置 ( i) // left 是 right 1 int i right; int j totalLeft - i; // 获取四个关键值注意处理越界 (INT_MIN / INT_MAX) int aLeftMax (i 0) ? INT_MIN : a[i - 1]; // a 左边最大 int bLeftMax (j 0) ? INT_MIN : b[j - 1]; // b 左边最大 int aRightMin (i m) ? INT_MAX : a[i]; // a 右边最小 int bRightMin (j n) ? INT_MAX : b[j]; // b 右边最小 // 计算中位数 if ((m n) % 2 1) { // 奇数取左边的最大值 return max(aLeftMax, bLeftMax); } else { // 偶数取 (左边最大 右边最小) / 2.0 return (max(aLeftMax, bLeftMax) min(aRightMin, bRightMin)) / 2.0; } } };