二分法查找

对于一个有序数组

int[] nums={0,1,2,3,4,5};

将它移位变为：

nums={3,4,5,0,1,2};

我们想找到其中的最小值该怎么做？
通常的方法是遍历数组中的每一个元素，比较得到最小值，他的时间复杂度为O(n)；
我们通过二分法可以将复杂度变为O(logn);
通过不断地二分数组，只分析目标所在的那二分之一，有大量数据的情况下，可以大大降低运行所需的时间。

我们要想找出nums数组中的最小值，首先声明三个指针，分别是左指针、右指针和中间指针：

int left=0;
int right=nums.length-1;
int mid=0;

然后我们开始二分：

while(left<right){
    mid=(left+right)/2;
    ...
}

观察数组的结构我们知道，右指针初始位置的数值一定小于左指针初始位置的数值，且从左指针到最小值之前都是增大的，从最小值到右指针也都是增大的。

二分法.png

直观比较.png

通过判断中间指针所指值的大小，我们可以知道目标值在左右哪一块，然后在将中间指针的值赋给左指针或右指针，再重新生成中间指针，我们就省去了原来数据数量基础上的一半的数值判断。

while(left<right){
    mid=(left+right)/2;
    if(nums[mid]<nums[right]){
        right=mid;//若mid处数值小于right处的，那么说明最小值在它的左边或者就在它这里，砍掉mid右边的一半;
    }else{
        left=mid+1;//若mid处数值大于right处的，那么说明最小值在它的右边或者就这他这里，砍掉mid左边的一半；
    }
}

由循环条件可知，最后left=right，得出了最小值在数组中的序列。

二分法可以利用到诸多有某些固定规律的问题当中，通过观察条件，灵活改变判断条件，可以有效提高运行效率。

最后再来一个例子：

峰值元素是指其值严格大于左右相邻值的元素。
给出一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，返回任何一个峰值所在位置即可。

例：

输入:int nums={1,2,1,3,6,3};
输出:1或4
2和6是峰值元素，你输出其中一个所在的序列。

通过分析题意，我们可以从任意一个元素开始找峰值，对于长度内的任意i，肯定有：nums[i-1]<nums[i]>nums[i+1]只要朝着数据增大的方向开始寻找，就一定能找到，那么我们不妨用二分法，将任取的元素定为mid，当nums[mid]<nums[mid+1]时，就砍掉左半边，反之则砍掉右半边，最终一定能找到峰值：

public int findLeap(int[] nums){
    int left=0;
    int right=nums.length;
    int mid=0;
    while(left<right){
          mid=(left+right)/2;
        if(nums[mid]<nums[mid+1]){
            left=mid+1;
        }else{
            right=mid;
        }
    }

    return left;
}