前言
国庆前最后一次打卡，国庆后继续开启，公众号bigsai回复进群欢迎加入打卡，如有帮助记得点赞收藏。
近期打卡记录：
LeetCode 32最长有效括号(困难) （本周）
LeetCode 30串联所有单词的子串&31下一个排列（上周）
LeetCode 27移除元素&28实现strStr()&29两数相除(上周)
二分查找我想大家都很熟悉，二分查找每次判断并比较元素所在区间进行压缩，每次都可以压缩一半的区间，所以压到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，回复进群加入打卡力扣！
LeetCode (二分小专题)33搜索旋转排序数组34在排序数组中查找元素的第一个和最后一个位置35搜索插入位置
