LeetCode (二分小專題)33搜尋旋轉排序陣列&34在排序陣列中查詢元素的第一個和最後一個位置&35搜尋插入位置

前言

國慶前最後一次打卡，國慶後繼續開啟，公眾號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，回覆進群加入打卡力扣！