前言
二分查找我想大家都很熟悉，二分查找每次判断并比较元素所在区间进行压缩，每次都可以压缩一半的区间，所以压到1个大小把它你想来看就是(最坏)扩散了n次到达原始长度。
很多题就是原始的二分，但很多题就是二分变种。
33搜索旋转排序数组
这题其实就是一个二分变种，加了一些其他的条件。每次的mid要根据判断如何移动.一个正常序列分成左右两个序列，并且都是递增的，没有相同的。
就拿中间mid的值大于target就有以下几种情况：
按照这样思路同理分析另一半一直求解即可。
ac代码为：
public int search(int[] nums, int target) { if(nums[0]==target)return 0; if(nums[nums.length-1]==target)return nums.length-1; int l=0;int r=nums.length-1; while (l<r) { int mid=(l+r)/2; //System.out.println(mid+" "+l+" "+r); if(nums[mid]==target)return mid; // 8 9 2 3 4 5 6 7 if(nums[mid]>target)//中间大于目标值 { if(nums[0]>target) {//最左侧都大于 只可能在右侧最小区域 if(nums[mid]<nums[0])//当前在右区域 { r=mid; } else { l=mid+1; } } else {最左侧小于目标值 向左 r=mid; } } // 8 9 2 3 4 5 6 7 else {//中间小于目标值 //如果在右侧区域往左 if(nums[nums.length-1]<target)//最右侧小于target 需要向左侧去 { if(nums[mid]<nums[nums.length-1])//当前 { r=mid; } else { l=mid+1; } } else //最右侧大于target 在小的区域内 { l=mid+1; } //System.out.println(1); } } return -1; }
34在排序数组中查找元素的第一个和最后一个位置
入门二分，注意找到一个值后进行左右方向寻找边界问题。ac代码为：
public int[] searchRange(int[] nums, int target) { int a[]= {-1,-1}; if(nums.length==1&&nums[0]==target) {a[0]=0;a[1]=0;return a;} if(nums.length==0)return a; int leftindex,rightindex; int left=0,right=nums.length-1; while (left<right) { //System.out.println(left+" "+right); int mid=(left+right)/2; if(nums[mid]==target) { leftindex=mid; rightindex=mid; while (leftindex>=0&&nums[leftindex]==target) {leftindex--;} while (rightindex<nums.length&&nums[rightindex]==target) {rightindex++;} a[0]=leftindex+1;a[1]=rightindex-1; return a; } else if (nums[mid]<target) { left=mid+1; } else { right=mid; } } if(nums[left]==target) { a[0]=left;a[1]=left; } return a; }
35搜索插入位置
这题需要注意的就是插入位置或者查找到的编号。经典二分不多说你懂的/
public int searchInsert(int[] nums, int target) { if(nums[0]>=target)return 0;//剪枝 if(nums[nums.length-1]==target)return nums.length-1;//剪枝 if(nums[nums.length-1]<target)return nums.length; int left=0,right=nums.length-1; while (left<right) { int mid=(left+right)/2; if(nums[mid]==target) return mid; else if (nums[mid]>target) { right=mid; } else { left=mid+1; } } return left; }
本次打卡结束拉，下周国庆暂停一次(就一次)。欢迎其他小哥哥小姐姐加入打卡，微信搜索bigsai，回复进群加入打卡力扣！
