33-搜尋旋轉排序數組

        整數數組 nums 按升序排列，數組中的值 互不相同 。在傳遞給函數之前，nums 在預先未知的某個下标 k（0 <= k < nums.length）上進行了 旋轉，使數組變為 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标從0開始計數）。例如， [0,1,2,4,5,6,7] 在下标 3 處經旋轉後可能變為 [4,5,6,7,0,1,2] 。給你旋轉後的數組 nums 和一個整數 target ，如果 nums 中存在這個目标值 target ，則傳回它的下标，否則傳回 -1 。如輸入：nums = [4,5,6,7,0,1,2], target = 0，輸出：4。

        這是一個轉換的二分查找算法的應用，對轉換後的數組進行切換之後，肯定有一部分是有序的。是以，這裡還是可以采用二分查找算法進行求解。具體解析過程見代碼注釋。難倒不難，主要是細節，比如說什麼時候要加上等于之類的。

package likouhot;
/*
 * 33.搜尋旋轉排序數組
 */
public class Demo33 {
	/*
	 * 将一個有序數組分成兩半，将前半部分挪到數組的後面，後半部分挪到前面。
	 * 1.可以采用二分查找算法
	 * 2.每一次做切分之後，肯定有一半是有序的
	 */
	  	public int search(int[] nums, int target) {
	  		int left = 0;
	  		int right = nums.length-1;
	  		while(left <= right) {
	  			int mid = (left+right)/2;
	  			int temp_left = nums[left];
	  			int temp_right = nums[right];
	  			int temp_mid = nums[mid];
	  			if(temp_mid == target) {
	  				return mid;
	  			}
	  			/*
	  			 * 1.左半部分有序，且target在左半部分,則right = mid-1;	
	  			 * 	1.1 在這裡需要注意的一個地方就是target可能等于左邊的第一個元素
	  			 *  1.2 還有一個地方需要注意的就是左邊可能隻有一個元素，是以要temp_left = temp_mid
	  			 * 2.左半部分有序，且target在右半部分，則left = mid+1;
	  			 * 3.右邊有序，且target在右半部分t,則left = mid+1;
	  			 * 	3.1 這裡同樣需要注意的就是可能target=temp_right
	  			 * 4.右邊有序，且target不在右邊，則right = mid-1;
	  			 */
	  			if(temp_left<=temp_mid) {
	  				if(target<temp_mid && target>=temp_left) {
	  					right = mid-1;	
	  				}else {
	  					left = mid+1;
	  				}
	  			} else {
	  				if(target<=temp_right && target>temp_mid) {
	  					left = mid+1;
	  				}else {
	  					right = mid-1;
	  				}
	  			}
	  		}
	       return -1;   
    }
	 
	  public static void main(String args[]) {
		  Demo33 demo = new Demo33();
		  int[] nums = {5,1,3};
		  System.out.println(demo.search(nums, 3));
	  }	
	  	
}