【leetcode】搜索旋轉(zhuǎn)排序數(shù)組

題目：

假設按照升序排序的數(shù)組在預先未知的某個點上進行了旋轉(zhuǎn)。

( 例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] )。

搜索一個給定的目標值，如果數(shù)組中存在這個目標值，則返回它的索引，否則返回 -1 。

你可以假設數(shù)組中不存在重復的元素。

你的算法時間復雜度必須是 O(log n) 級別。

示例 1:

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

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

思路：

時間復雜度lgn,考慮用二分查找，二分搜索法的關鍵在于獲得了中間數(shù)后，判斷下面要搜索左半段還是右半段，我們觀察上面紅色加粗的數(shù)字都是升序的，由此我們可以觀察出規(guī)律，如果中間的數(shù)小于最右邊的數(shù)，則右半段是有序的，若中間數(shù)大于最右邊數(shù)，則左半段是有序的，我們只要在有序的半段里用首尾兩個數(shù)組來判斷目標值是否在這一區(qū)域內(nèi)，這樣就可以確定保留哪半邊了。

java代碼：

class Solution {
    public int search(int[] nums, int target) {
        if(nums == null || nums.length==0) {
            return -1;
        }
 
        int left = 0;
        int right = nums.length-1;
        while (left<=right) {
            int mid = (right+left)/2;
            if(nums[mid] == target) {
                return mid;
            }else  if(nums[mid]<nums[right]) {
                if(nums[mid]<target&&nums[right]>=target) {
                    left = mid+1;
                }else {
                    right = mid -1;
                }
            }else {
                if(nums[left]<=target&&nums[mid]>target) {
                    right = mid -1;
                }else {
                    left = mid+1;
                }
            }
        }
 
        return -1;
    }
}