代码随想录Day1

数组

二分查找

力扣704.二分查找

二分查找有几个最重要的特点：

1. 对于需要用到”二分查找“的数组来说（即用二分查找来找到确切的某一个元素），这个数组中的元素不能重复；

2. 被操作的数组一定要是有序的，如果没有排好序，则需要先排好序再使用二分查找。

class Solution {public int search(int[] nums, int target) {int left=0;int right=nums.length-1;while(left<=right){//这里最好不要使用(left+right)/2，因为有越界的风险存在int mid=left+(right-left)/2;if(target<nums[mid]){right=mid-1;}else if(target>nums[mid]){left=mid+1;}else{return mid;}}return -1;}
}

在排序数组中查找元素的第一个和最后一个位置

力扣34.在排序数组中查找元素的第一个和最后一个位置

注： 此题体现出二分查找另一个最重要的作用，找出某个元素的”边界“

class Solution {public int[] searchRange(int[] nums, int target) {int left=0;int right=nums.length-1;//数组为中没有元素，或者目标值根本不可能存在（即小于数组最小值或者大于数组最大值/*这里有两点要注意：1、根据题意，输入的数组不为null，而是没有元素。（表示数组为null的写法为 nums==null,但是此题要写为nums.length==02、nums.length==0 必须要写在最前面。根据||的使用规则，如果将target>nums[right]写在最前面，会直接报错。（因为如果nums.length==0  那么right此时就是-1）*/if(nums.length==0 || target<nums[left] || target>nums[right])return new int[]{-1,-1};int leftBorder=-1,rightBorder=-1;leftBorder=getLeftBorder(nums,target);rightBorder=getRightBorder(nums,target);if(rightBorder-leftBorder>1)return new int[]{leftBorder+1,rightBorder-1};else return new int[]{-1,-1};}int getRightBorder(int[] nums, int target){int left=0;int right=nums.length-1;int rightBorder=-1;while(left<=right){int mid=left+(right-left)/2;if(target<nums[mid]){right=mid-1;}else{left=mid+1;rightBorder=left;}}return rightBorder;}int getLeftBorder(int[] nums, int target){int left=0;int right=nums.length-1;int leftBorder=-1;while(left<=right){int mid=left+(right-left)/2;if(target>nums[mid]){left=mid+1;}else{right=mid-1;leftBorder=right;}}return leftBorder;}}

最抽象的是getRightBorder()方法以及getLeftBorder()方法

• 如果暂且忽略掉上面两个方法中的leftBorder、rightBorder变量，而仅是观察两方法的写法，大体上与二分查找相似，唯一不同点在于（拿getLeftBorder()方法为例）：

//其关键代码为：
while(left<=right){int mid=left+(right-left)/2;if(target>nums[mid]){left=mid+1;}else{right=mid-1;leftBorder=right;}
}//略微再多改写一下也就是while(left<=right){int mid=left+(right-left)/2;if(target>nums[mid]){left=mid+1;}else if(traget<nums[mid]){right=mid-1;    leftBorder=right;}
/*以上两个就跟二分查找一样了，当target>nums[mid]   left=mid+1;  当target<nums[mid] right=mid-1
*/
//但是！ 下面这种情况，target==nums[mid]的时候，为什么还是right=mid-1，并且leftborder=right;
//个人理解：因为left是一直往右移动的，right是一直往左移动的。找左边界，只能是右‘指针’往左走。并且在while(left<=right)的条件下，如果target确实存在于nums中的话，left与right一定是不包含target的下标的。else{right=mid-1;leftBorder=right; }}

其次：为什么一定要if(rightBorder-leftBorder>1)；才 return new int[]{leftBorder+1,rightBorder-1}; 即表示这为什么一定是rightBorder-leftBorder>1 才表示target确实在nums中存在？

• 如果target只有一个，且下标为5，那么求出来的rightBorder为6，leftBorder为4。6-4>1 显然正确。
• 如果target根本不存在于nums，可以想见，最后left、right、mid都指向同一个元素，而这个元素不可能同时满足大于并小于target，所以这个时候不是left+1 就是 right-1，最终rightBorder-leftBorder==1。 确实没有大于1