陕西建工第五建设集团有限公司官方网站,app软件开发官网,专业团队的句子,智能网站建设平台代码随想录Day1
数组
二分查找
力扣704.二分查找
二分查找有几个最重要的特点#xff1a; 对于需要用到”二分查找“的数组来说#xff08;即用二分查找来找到确切的某一个元素#xff09;#xff0c;这个数组中的元素不能重复#xff1b; 被操作的数组一定要是有序的…代码随想录Day1
数组
二分查找
力扣704.二分查找
二分查找有几个最重要的特点 对于需要用到”二分查找“的数组来说即用二分查找来找到确切的某一个元素这个数组中的元素不能重复 被操作的数组一定要是有序的如果没有排好序则需要先排好序再使用二分查找。
class Solution {public int search(int[] nums, int target) {int left0;int rightnums.length-1;while(leftright){//这里最好不要使用(leftright)/2因为有越界的风险存在int midleft(right-left)/2;if(targetnums[mid]){rightmid-1;}else if(targetnums[mid]){leftmid1;}else{return mid;}}return -1;}
}在排序数组中查找元素的第一个和最后一个位置
力扣34.在排序数组中查找元素的第一个和最后一个位置
注 此题体现出二分查找另一个最重要的作用找出某个元素的”边界“
class Solution {public int[] searchRange(int[] nums, int target) {int left0;int rightnums.length-1;//数组为中没有元素或者目标值根本不可能存在即小于数组最小值或者大于数组最大值/*这里有两点要注意1、根据题意输入的数组不为null而是没有元素。表示数组为null的写法为 numsnull,但是此题要写为nums.length02、nums.length0 必须要写在最前面。根据||的使用规则如果将targetnums[right]写在最前面会直接报错。因为如果nums.length0 那么right此时就是-1*/if(nums.length0 || targetnums[left] || targetnums[right])return new int[]{-1,-1};int leftBorder-1,rightBorder-1;leftBordergetLeftBorder(nums,target);rightBordergetRightBorder(nums,target);if(rightBorder-leftBorder1)return new int[]{leftBorder1,rightBorder-1};else return new int[]{-1,-1};}int getRightBorder(int[] nums, int target){int left0;int rightnums.length-1;int rightBorder-1;while(leftright){int midleft(right-left)/2;if(targetnums[mid]){rightmid-1;}else{leftmid1;rightBorderleft;}}return rightBorder;}int getLeftBorder(int[] nums, int target){int left0;int rightnums.length-1;int leftBorder-1;while(leftright){int midleft(right-left)/2;if(targetnums[mid]){leftmid1;}else{rightmid-1;leftBorderright;}}return leftBorder;}}最抽象的是getRightBorder()方法以及getLeftBorder()方法
如果暂且忽略掉上面两个方法中的leftBorder、rightBorder变量而仅是观察两方法的写法大体上与二分查找相似唯一不同点在于拿getLeftBorder()方法为例
//其关键代码为
while(leftright){int midleft(right-left)/2;if(targetnums[mid]){leftmid1;}else{rightmid-1;leftBorderright;}
}//略微再多改写一下也就是while(leftright){int midleft(right-left)/2;if(targetnums[mid]){leftmid1;}else if(tragetnums[mid]){rightmid-1; leftBorderright;}
/*以上两个就跟二分查找一样了当targetnums[mid] leftmid1; 当targetnums[mid] rightmid-1
*/
//但是 下面这种情况targetnums[mid]的时候为什么还是rightmid-1并且leftborderright;
//个人理解因为left是一直往右移动的right是一直往左移动的。找左边界只能是右‘指针’往左走。并且在while(leftright)的条件下如果target确实存在于nums中的话left与right一定是不包含target的下标的。else{rightmid-1;leftBorderright; }}其次为什么一定要if(rightBorder-leftBorder1)才 return new int[]{leftBorder1,rightBorder-1}; 即表示这为什么一定是rightBorder-leftBorder1 才表示target确实在nums中存在
如果target只有一个且下标为5那么求出来的rightBorder为6leftBorder为4。6-41 显然正确。如果target根本不存在于nums可以想见最后left、right、mid都指向同一个元素而这个元素不可能同时满足大于并小于target所以这个时候不是left1 就是 right-1最终rightBorder-leftBorder1。 确实没有大于1
