[数据结构与算法]LeetCode 热题100-17-搜索旋转排序数组

核心思想：二分法

class Solution {
    public int search(int[] nums, int target) {
        int len = nums.length;
        if(len == 0){
            return -1;
        }
        int left = 0;
        int right = len-1;
        int mid; 
        int result;
        while(left <= right){
            mid = (left + right)/2;
            if(nums[mid] == target){
                return mid;
            }
            //判断是否为有序序列，必有一半是有序的
            if(nums[left] <= nums[mid]){
            	//判断是否在有序序列中
                if(nums[left] <= target && target < nums[mid]){
                    right = mid - 1;
                }else{
                	//不在序列中则去另一半不有序的中寻找
                    left = mid + 1;
                }
            }else{
                if(nums[mid] < target && target <= nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

二分法有递归版和非递归版，本算法为非递归版本。
二分法（递归版）：

public static int BinarySearch(int key,int[] arr,int low,int high)
	{
		if(low > high)
			return -1;
		int mid = low + (high - low)/2;
		if(key < arr[mid])
			return BinarySearch(key,arr,low,mid-1);
		else if(key > arr[mid])
			return BinarySearch(key,arr,mid+1,high);
		else
			return mid;
	}

二分法（非递归版）：

public static int BinarySearch(int key,int[] a)
	{
		int low = 0;
		int high = a.length - 1;
		while(low <= high)
		{
			//high – low 的方式比 (high+low)/2安全
			int mid = low + (high - low)/2;
			if(key < a[mid])
				high = mid - 1;       //显然是不包括mid的
			else if(key > a[mid])
				low = mid + 1;
			else
				return mid;
		}
		return -1;
	}