搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 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

思想：二分查找，先找到旋转点，继续用二分查找

package com.imooc.demo;

public class hello{
    public static void main(String[] args)
    {
        Solution so = new Solution();
        int[] nums = {1,3,5};
        int res = so.search(nums,3);
        System.out.println(res);
    }
}
class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==0)
            return -1;
        if(nums.length==1)
            return nums[0]==target?0:-1;
        if(nums[0] < nums[nums.length-1])
            return bi_search(nums,target,0,nums.length-1);
        int i=0,j=nums.length-1;
        while(i<=j)
        {
            int k = i+(int)(j-i)/2;
            if(nums[k]>nums[i])
            {
                i=k;
            }
            if(nums[k]<nums[i])
            {
                j=k;
            }
            if(i+1==j)
                break;
        }
        if(nums[0]<=target && target<=nums[i])
            return bi_search(nums,target,0,i);
        if(nums[j]<=target && target<=nums[nums.length-1])
            return bi_search(nums,target,j,nums.length-1);
        return -1;
    }

    public int bi_search(int[] nums, int target, int i, int j)
    {
        while(i <= j)
        {
            int k = i + (int)(j-i)/2;
            if(nums[k] > target)
            {
                j = k-1;
            }
            else if(nums[k] < target)
            {
                i = k+1;
            }else{
                return k;
            }
        }
        return -1;
    }
}