前言

國慶前最后一次打卡，國慶后繼續開啟，公眾號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搜索插入位置的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。