34. 在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。关键:循环不变量L-1始终是红色(红色小于target的数)R1始终是蓝色(蓝色大于target的数)根据循环不变量R1是我们要找的答案 由于循环结束后R1L所以答案也可以用L表示 思路 这篇文章https://blog.csdn.net/groovy2007/article/details/78309120里那句“关键不在于区间里的元素具有什么性质而是区间外面的元素具有什么性质。”之后醍醐灌顶建立了我自己的二分查找心智模型和up主的有些类似。 也就是看最终左右指针会停在哪里。 如果我们要找第一个大于等于x的位置那么我就假设L最终会停在第一个大于等于x的位置R停在L的左边。 这样按照上面那句话可以把循环不变式描述为“L的左边恒小于xR的右边恒大于等于x”这样一来其他的各种条件就不言自明了。 根据二分查找改编1、假设left指向大于等于target的位置 而right指向小于target的位置2、二叉法有四种情况大于等于大于小于等于小于3、lower_bound返回的left永远指向大于等于target情况所以是第一种情况大于等于4、大于可以转换成(target1)小于等于可以转换成(target)的位置的基础上再减1小于可以转换成(target)的位置的基础上再减1代码classSolution{//开始位置是结束位置是//假设left指向大于等于target的位置 而right指向小于target的位置//二叉法有四种情况大于等于大于小于等于小于//lower_bound返回的left永远指向大于等于target情况publicintlowerBound(int[]nums,inttarget){intleft0;intrightnums.length-1;// int mid left (right-left)/2;while(leftright){intmid(leftright)/2;if(nums[mid]target){leftmid1;}else{rightmid-1;}}returnleft;}publicint[]searchRange(int[]nums,inttarget){intstartlowerBound(nums,target);if(startnums.length||nums[start]!target){returnnewint[]{-1,-1};}intendlowerBound(nums,target1)-1;returnnewint[]{start,end};}}162. 寻找峰值峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 **任何一个峰值** 所在位置即可。 你可以假设 nums[-1] nums[n] -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题思路1、根据红蓝染色法来做红色表示某一个峰顶左侧蓝色表示为某一个峰顶右侧2、初始比较nums[mid]与nums[mid1]关系ifnums[mid]nums[mid1],那么就可以把[0,mid]之间都染成红色因为这个区间必然在某一个峰顶的左侧。则要确认另外一个区间的颜色。此时移动left。ifnums[mid]nums[mid1],那么就可以把[mid,n-1]之间都染成蓝色因为这个区间要么是峰顶要么峰顶左侧。也要确认另外一个区间的颜色。此时移动right。 代码classSolution{publicintfindPeakElement(int[]nums){//红蓝染色法红色表示峰顶的左侧蓝色表示峰顶或者峰顶的右侧intleft0;// nums[n] -∞,那么n-1的位置要么是峰顶要么是峰顶右侧所以必然是蓝色intrightnums.length-2;while(leftright){intmid(leftright)/2;if(nums[mid]nums[mid1]){//[0,mid]是红色在峰顶左边leftmid1;//要确认[mid1,n-2]的颜色}else{//[mid,n-2]是蓝色在峰顶右边rightmid-1;//要确认[0,mid-1]位置}}returnleft;}}153. 寻找旋转排序数组中的最小值已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 **旋转** 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到 - 若旋转 4 次则可以得到 [4,5,6,7,0,1,2] - 若旋转 7 次则可以得到 [0,1,2,4,5,6,7] 注意数组 [a[0], a[1], a[2], ..., a[n-1]] **旋转一次** 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个元素值 **互不相同** 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 **最小元素** 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题思路1、根据红蓝染色法的思路红色表示最小值的左侧蓝色表示最小值或者最小值的右侧。2、注意的是比较规则是mid和最后一个数比较而nums数组要么是一段递增的数组要么是两段递增的数组且第一段递增的数组比第二段递增的数组要高。3、ifnums[mid]nums[n-1],那么nums可以是一段递增的数组也可以是两段递增的数组ifnums[mid]nums[n-1],那么nums只能是两段递增的数组。4、数组中最后一个数肯定是蓝色要么是最小值要么是最小值的右侧 代码classSolution{publicintfindMin(int[]nums){//蓝色为最小值或者最小值的右侧//红色为最小值左侧if(nums.length1){returnnums[0];}intleft0;intnnums.length;intrightn-2;//n-1的位置必然是蓝色while(leftright){intmid(leftright)/2;if(nums[mid]nums[n-1]){//[mid,n-1]为蓝色rightmid-1;}else{//[0,mid]为红色leftmid1;}}returnnums[left];}}33. 搜索旋转排序数组整数数组 nums 按升序排列数组中的值 **互不相同** 。 在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 **向左旋转**使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 **从 0 开始** 计数。例如 [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 **旋转后** 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。思路1、根据红蓝染色法蓝色表示target或者target的右侧红色表示target的左侧2、要判断mid和target是否在同一段因为在同一段以及不同段的数组染色的方式不同。3、如果mid和target在同一段即ifmidend表示mid在后一段那么midtarget时 or targetend时就能确定[mid,n-1]之间的区间是蓝色。ifmidend,表示mid在前一段那么midtarget and targetend才能保证[mid,n-1]之间的区间是蓝色。 其他的情况只能保证mid之前是红色。 ps:要注意nums[mid]target中的等号,如果去掉等号就不对了因为midtarget时不会把mid染成蓝色。 代码classSolution{publicbooleanis_blue(intmid,int[]nums,inttarget){intnnums.length;if(nums[mid]nums[nums.length-1]){//mid在后半段returnnums[mid]target||targetnums[n-1];//[mid,n-1]是蓝色,要注意nums[mid]target中的等号}else{//mid 在前半段returnnums[mid]targettargetnums[n-1];//[mid,n-1]是蓝色}}publicintsearch(int[]nums,inttarget){//蓝色表示target的右侧红色表示target左侧//仍然是两段递增的数组intleft0;intnnums.length;intrightn-2;//n-1的位置要么是target要么是target的右侧,是蓝色while(leftright){intmid(leftright)/2;if(is_blue(mid,nums,target)){//[mid,n-1]是蓝色已经确定rightmid-1;}else{//[0,mid]是红色已经确定leftmid1;}}returntargetnums[left]?left:-1;}}
【基础算法精讲 04】二分查找 红蓝染色法
发布时间：2026/6/10 18:59:29
34. 在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。关键:循环不变量L-1始终是红色(红色小于target的数)R1始终是蓝色(蓝色大于target的数)根据循环不变量R1是我们要找的答案 由于循环结束后R1L所以答案也可以用L表示 思路 这篇文章https://blog.csdn.net/groovy2007/article/details/78309120里那句“关键不在于区间里的元素具有什么性质而是区间外面的元素具有什么性质。”之后醍醐灌顶建立了我自己的二分查找心智模型和up主的有些类似。 也就是看最终左右指针会停在哪里。 如果我们要找第一个大于等于x的位置那么我就假设L最终会停在第一个大于等于x的位置R停在L的左边。 这样按照上面那句话可以把循环不变式描述为“L的左边恒小于xR的右边恒大于等于x”这样一来其他的各种条件就不言自明了。 根据二分查找改编1、假设left指向大于等于target的位置 而right指向小于target的位置2、二叉法有四种情况大于等于大于小于等于小于3、lower_bound返回的left永远指向大于等于target情况所以是第一种情况大于等于4、大于可以转换成(target1)小于等于可以转换成(target)的位置的基础上再减1小于可以转换成(target)的位置的基础上再减1代码classSolution{//开始位置是结束位置是//假设left指向大于等于target的位置 而right指向小于target的位置//二叉法有四种情况大于等于大于小于等于小于//lower_bound返回的left永远指向大于等于target情况publicintlowerBound(int[]nums,inttarget){intleft0;intrightnums.length-1;// int mid left (right-left)/2;while(leftright){intmid(leftright)/2;if(nums[mid]target){leftmid1;}else{rightmid-1;}}returnleft;}publicint[]searchRange(int[]nums,inttarget){intstartlowerBound(nums,target);if(startnums.length||nums[start]!target){returnnewint[]{-1,-1};}intendlowerBound(nums,target1)-1;returnnewint[]{start,end};}}162. 寻找峰值峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 **任何一个峰值** 所在位置即可。 你可以假设 nums[-1] nums[n] -∞ 。 你必须实现时间复杂度为 O(log n) 的算法来解决此问题思路1、根据红蓝染色法来做红色表示某一个峰顶左侧蓝色表示为某一个峰顶右侧2、初始比较nums[mid]与nums[mid1]关系ifnums[mid]nums[mid1],那么就可以把[0,mid]之间都染成红色因为这个区间必然在某一个峰顶的左侧。则要确认另外一个区间的颜色。此时移动left。ifnums[mid]nums[mid1],那么就可以把[mid,n-1]之间都染成蓝色因为这个区间要么是峰顶要么峰顶左侧。也要确认另外一个区间的颜色。此时移动right。 代码classSolution{publicintfindPeakElement(int[]nums){//红蓝染色法红色表示峰顶的左侧蓝色表示峰顶或者峰顶的右侧intleft0;// nums[n] -∞,那么n-1的位置要么是峰顶要么是峰顶右侧所以必然是蓝色intrightnums.length-2;while(leftright){intmid(leftright)/2;if(nums[mid]nums[mid1]){//[0,mid]是红色在峰顶左边leftmid1;//要确认[mid1,n-2]的颜色}else{//[mid,n-2]是蓝色在峰顶右边rightmid-1;//要确认[0,mid-1]位置}}returnleft;}}153. 寻找旋转排序数组中的最小值已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 **旋转** 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到 - 若旋转 4 次则可以得到 [4,5,6,7,0,1,2] - 若旋转 7 次则可以得到 [0,1,2,4,5,6,7] 注意数组 [a[0], a[1], a[2], ..., a[n-1]] **旋转一次** 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个元素值 **互不相同** 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 **最小元素** 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题思路1、根据红蓝染色法的思路红色表示最小值的左侧蓝色表示最小值或者最小值的右侧。2、注意的是比较规则是mid和最后一个数比较而nums数组要么是一段递增的数组要么是两段递增的数组且第一段递增的数组比第二段递增的数组要高。3、ifnums[mid]nums[n-1],那么nums可以是一段递增的数组也可以是两段递增的数组ifnums[mid]nums[n-1],那么nums只能是两段递增的数组。4、数组中最后一个数肯定是蓝色要么是最小值要么是最小值的右侧 代码classSolution{publicintfindMin(int[]nums){//蓝色为最小值或者最小值的右侧//红色为最小值左侧if(nums.length1){returnnums[0];}intleft0;intnnums.length;intrightn-2;//n-1的位置必然是蓝色while(leftright){intmid(leftright)/2;if(nums[mid]nums[n-1]){//[mid,n-1]为蓝色rightmid-1;}else{//[0,mid]为红色leftmid1;}}returnnums[left];}}33. 搜索旋转排序数组整数数组 nums 按升序排列数组中的值 **互不相同** 。 在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 **向左旋转**使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 **从 0 开始** 计数。例如 [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 **旋转后** 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。 你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。思路1、根据红蓝染色法蓝色表示target或者target的右侧红色表示target的左侧2、要判断mid和target是否在同一段因为在同一段以及不同段的数组染色的方式不同。3、如果mid和target在同一段即ifmidend表示mid在后一段那么midtarget时 or targetend时就能确定[mid,n-1]之间的区间是蓝色。ifmidend,表示mid在前一段那么midtarget and targetend才能保证[mid,n-1]之间的区间是蓝色。 其他的情况只能保证mid之前是红色。 ps:要注意nums[mid]target中的等号,如果去掉等号就不对了因为midtarget时不会把mid染成蓝色。 代码classSolution{publicbooleanis_blue(intmid,int[]nums,inttarget){intnnums.length;if(nums[mid]nums[nums.length-1]){//mid在后半段returnnums[mid]target||targetnums[n-1];//[mid,n-1]是蓝色,要注意nums[mid]target中的等号}else{//mid 在前半段returnnums[mid]targettargetnums[n-1];//[mid,n-1]是蓝色}}publicintsearch(int[]nums,inttarget){//蓝色表示target的右侧红色表示target左侧//仍然是两段递增的数组intleft0;intnnums.length;intrightn-2;//n-1的位置要么是target要么是target的右侧,是蓝色while(leftright){intmid(leftright)/2;if(is_blue(mid,nums,target)){//[mid,n-1]是蓝色已经确定rightmid-1;}else{//[0,mid]是红色已经确定leftmid1;}}returntargetnums[left]?left:-1;}}
