二分查找

二分查找是一种比较快速的查找方法，也比较常用，二分查找基于数组这种数据结构，并且要求查找的目的数组时有序的，其实看一下二分查找的原理便能理解为何要求是有序的数组。确实，算法第四版是这么写的“二分查找的数组是要求有序的”，但是在做题的过程中发现，有些题目的数组元素时无序的，但是也可以用二分查找，因为二分查找比较快，时间复杂度为O（logN），因此，使用二分查找并非是能在有序数组上使用，只要是在一次迭代之后查找范围缩小一半，即是二分查找。

关于有序数组的二分查找的两种实现方式及无序数组的二分查找请看后面的leetcode题目来理解。

二分查找的原理，由于查找的目的数组时有序的，因此可以按照以下思路进行查找（查找的结果是目的值在数组中的位置比如0,1,2,3,4,5......），我们每次比较当前子数组的中间位置的元素值是否和我们查找的值（target）相同，如果相同，则说明该位置便是我们要找的，返回即可，如果不想等，则有两种情况，如果目的值比当前中间元素值小，则继续查找左边一半（当前子树组被中间元素分为两半，分别是左边一半和右边一半）；如果目的值比当前中间元素大，则继续查找右边一半。直到找到目的值，或者是已经把子数组的大小缩小到负的，则应停止查找，目的值不在查找的数组中，返回-1，或是根据具体情况返回其他的值。

二分查找的实现，二分查找有两种实现方式，分别是递归实现和迭代实现，其实两种实现方式非常相似，下面以一道leetcode上的题目来说明这两种实现方式。

leetcode704题二分查找

题目描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在则返回下标，否则返回 -1。

示例 1:输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例 2:输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

提示：假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。

下面是递归的方式实现的二分查找，只要找好递归终止时的返回值，和终止条件，以及边界的处理，递归的方法比较好写。在提交这道题时，递归的方法实现耗时4ms。

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(target, 0, nums.length-1, nums);
    }
    
    private int binarySearch(int target, int lo, int hi, int[] nums){
        if(hi < lo)
            return -1;
        int mid = lo + (hi - lo) / 2;
        int compareResult = target - nums[mid];
        if(compareResult < 0)
            return binarySearch(target, lo, mid-1, nums);
        else if(compareResult > 0)
            return binarySearch(target, mid+1, hi, nums);
        else
            return mid;
    }
}

下面是迭代的方法实现，迭代的实现和递归非常相似，只要递归懂了，很容易修改成迭代，其实任何递归的代码都可以用while循环来改写实现，提交时耗时3ms。

class Solution {
    public int search(int[] nums, int target) {
        return binarySearch(nums, target);
    }
    
    private int binarySearch(int[] nums, int target){
        int lo = 0;
        int hi = nums.length - 1;
        int mid = 0;
        int compareResult = 0;
        while(hi>=lo){
            mid = lo + (hi - lo) / 2;
            compareResult = target - nums[mid];
            if(compareResult < 0)
                hi = mid - 1;
            else if(compareResult > 0)
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

二分查找不仅可以用于有序数组，也可以用在无序数组上面。关于无序数组中使用二分查找，请看下面这道题目：

leetcode162题，寻找峰值

题目描述：

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回

其索引。数组可能包含多个峰值，这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n]=-∞。

示例 1:输入: nums = [1,2,3,1] 输出: 2 解释: 3 是峰值元素，你的函数应该返回其索引 2。

示例 2:输入: nums = [1,2,1,3,5,6,4] 输出: 1 或 5 解释: 你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5，

其峰值元素为 6。

说明:你的解法应该是 O(logN) 时间复杂度的。

解决思路：由于题目要求解决方法的时间复杂度是对数时间复杂度，因此想到查找一个元素的对数时间复杂度的查找方法时二分查找。因此应该使用二分查找，虽然这个题目的原始数组并不是有序的，但是仔细思考题目的条件和要求发现，二分查找也可以用在此无序数组上面。目的是查找出峰值元素所在的位置来，那么使用二分查找，每次比较当前元素是否大于左右两个元素的值，如果大于则说明此元素是峰值元素，否则则考虑此元素与左右元素的大小关系，大于该元素的左右其中的某个元素可能是峰值元素，因此得到新的lo或者是新的hi，继续查找，直到找到峰值元素，注意对边界的处理，尤其是此题目超出数组索引的元素都认为是无穷小，因此边界元素是有可能为峰值元素的。

代码如下：

class Solution {
    public int findPeakElement(int[] nums) {
        int lo = 0;
        int hi = nums.length-1;
        int mid = 0;
        while(hi>=lo){
            mid = lo + (hi-lo)/2;
            if((mid==lo||nums[mid]>nums[mid-1])&&(mid==hi||nums[mid]>nums[mid+1]))
                return mid;
            if(nums[mid]<nums[mid+1])
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        return lo;
    }
}