SearchInRotatedAry

其实这个问题，是基于二分查找（BinarySearch）来解决的。所以这里需要先理解一下二分查找。

1. 二分查找

二分查找，也叫做折半查找。顾名思义，是每一次折半，从而提升查找效率。
需要三个指针，left，right，mid，每次判断mid的值是否等于 target，从而调整 left 和 right 的值，达到每次折半的效果。
这里有一个前提，就是二分查找的数组，一定要是 有序数组。这是调整 left 和 right 就可以折半的原因。

代码

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

    }

    public static void main(String[] args){
        int a[] = {1,2,3,4,6,9,12};
        BinarySearch b = new BinarySearch();
        System.out.println(b.search(a,12));
    }
}

2. SearchInRotatedAry

在上面的BinaryResearch的基础上，现在来看这个问题。

问题描述

给出一个在某个点翻转的升序数列。寻找出最小的元素。但是要求时间复杂度是 O(logn)。
用例：[4,5,6,7,0,1,2] ，tar=0 Output : 4
[4,5,6,7,0,1,2]，tar=3 Output：-1

分析

看到这个对数时间复杂度，很明白这里就是要用divide and conquer 的思想，也就是二分查找。但是问题的关键是，整个数列不是升序排列的，每次判断玩 mid 和 tar 的关系之后，怎样调整 left 和 right 指针从而折半，是整个问题的关键。

思路

尽管整个数组不是升序的，但是可以判断出来前半个或者后半个是有序的，在这个有序的基础上，就可以判断 tar 是否在这个有序的数组内，进而缩小搜索范围。

代码

package day_6;

public class SearchInRotatedSortedArray {
    public int search(int[] nums, int target){
        int count = nums.length;
        if(count==0)
            return -1;
        if(count==1)
            if(nums[0]==target)
                return 0;
            else
                return -1;
        int left = 0;
        int right = count-1;

        while (left <= right){  // 高级版的二分查找
            int mid = (left+right)/2;
            System.out.println(mid);
            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[mid]>target && nums[left]<= target)
                    right = mid-1;
                else left = mid+1;
                }
            }
        }
        return  -1;
    }

    public  static void main(String[] args){
    int a[] ={4,5,6,7,0,1,2};
    SearchInRotatedSortedArray s = new SearchInRotatedSortedArray();
    System.out.print(s.search(a,3));
    }
}