搜尋旋轉排序數組（二分法實作）

題目

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。( 例如，數組 [0,1,2,4,5,6,7] 可能變為 [4,5,6,7,0,1,2] )。搜尋一個給定的目标值，如果數組中存在這個目标值，則傳回它的索引，否則傳回 -1 。

注意：

1、你可以假設數組中不存在重複的元素。

2、你的算法時間複雜度必須是 O(log n) 級别。

示例 :

輸入: nums = [4,5,6,7,0,1,2], target = 0

輸出: 4

思路

1、算法時間複雜度必須是 O(log n) 級别，第一想到的就是二分法；

2、雖然數組是部分有序的，但通過二分法可以分出一部分是有序的，一部分是無序的，我們隻需要判斷目标值（target）是否在有序序列中，來決定left和right的選取。

3、核心程式設計思路：

• 如果左邊有序（[left, mid]），則判斷目标值是否在有序序列中，如果在，則right = mid - 1；否則，在右邊部分有序的數組中，則left = mid + 1;
• 如果右邊有序（[left, mid]），則判斷目标值是否在有序序列中，如果在，則left = mid + 1；否則，在左邊部分有序的數組中，則right = mid - 1;

實作

public int search(int[] nums, int target) {
        if(nums == null) return -1;
        if(nums.length == 1) return nums[0] == target ? 0 : -1;

        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
           int mid = (left + right) / 2;
           if(nums[mid] == target) return mid;
			
           if(nums[left] <= nums[mid]){//(left, mid)有序  		
                if(nums[left] <= target && target < nums[mid]){
                //目标數值在有序序列中
                    right = mid - 1;
                }else{
                //目标數值不在有序序列中
                    left = mid + 1;
                }
            }else{//(mid, right)有序
                if(nums[mid] < target && target <= nums[right]){
                //目标數值在有序序列中
                    left = mid + 1;
                }else{
                //目标數值不在有序序列中
                    right = mid - 1;
                }
            }
        }
        return -1;
    }