二分查找是比较常见的查找算法，但是它需要一个条件就是数组有序，因此当面试中听到有序数组这个关键词的时候，不妨往二分查找法想一想，或许它就是解开问题的钥匙。

算法思想：

注意该算法的前提条件：有序数组。想查找元素value，先查看数组中间元素值v与value的大小，若相等则刚好，否则根据比较结果选择左、右半部分再次寻找。

时间复杂度：

整个查找过程可构成一棵树，时间复杂度为O(logn)。

问题1

给定一个有序的数组，查找value是否在数组中，不存在返回-1。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class BinarySearch {
	/*
	 * arr:数组
	 * n:数组数据长度
	 * target:就是要查找的被返回的值
	 * while循环迭代的方式实现二分查找
	 */
	public static int binarySearch(int arr[], int n, int target){
	    // 在arr[l...r]之中查找target
	    int lo = 0, hi = n-1;
	    while( lo <= hi ){

	        //int mid = (l + r)/2;防止极端情况下的整形溢出，使用下面的逻辑求出mid
	        int mid = lo + (hi-lo)/2;

	        if( arr[mid] == target )
	            return mid;

	        if( arr[mid] > target )
	            hi = mid - 1;
	        else
	            lo = mid + 1;
	    }
	    return -1;
	}
	
	/*
	 * 递归的方式实现二分查找
	 */
	public static int binarySearch2(int arr[], int lo, int hi, int target){

	    if( lo > hi )
	        return -1;

	    int mid = lo + (hi-lo)/2;

	    if( arr[mid] == target )
	        return mid;
	    else if( arr[mid] > target )
	        return binarySearch2(arr, lo, mid-1, target);
	    else
	        return binarySearch2(arr, mid+1, hi, target);
	}
	
}

问题2

image

这就是一道经典的用二分查找解决的问题。下面给出解题答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + (right - left) / 2 ;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                //这边相等的话，就要找它周围的数字是否相等，直到找到一个区间为止
                int low = mid;
                int high = mid;
                while(low - 1 >= 0 && nums[low-1] == target){
                    low--;
                }
                while(high + 1 <= nums.length-1 && nums[high+1] == target){
                    high++;
                }
                res[0] = low;
                res[1] = high;
                return res;
            }
        }
        res[0] = -1;
        res[1] = -1;
        return res;
    }
}

其实我的思路很简单，就是在找到符合条件的mid之后，我就尝试在mid的两边再去找是否有相等的数字，由于是递增的数组，所以很好判断。

问题3

image

这是《剑指offer》上的一道题目，原本的数列一个非递减的序列，这里在中间咔了一刀变成两截，并且颠倒，那么就被划成了两段非递减的序列，并且前面的非递减数列要比后面的非递减数列要大于等于。所以，是有一定的规律的，这里还是推荐使用二分查找，只是是二分查找法的变体了。

当然了这个题目的暴力解法其实已经很简单了，就是从头开始遍历，只要出现一个数比前面一个数小，那么这个数就是原来序列的最前面的数，那么其实就是最小的数。

而二分查找在比较极端的条件下，比如元素都相等，可能就会退化为O(n)复杂度，但是如果原来的数列是一个严格递增的数列，那么还是快一点的。因为缩小的范围比较快。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length-1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(array[mid] > array[right]){
                //最小的元素一定在mid后面
                left = mid + 1;
            }else if(array[mid] < array[right]){
                //最小的元素在mid或者mid之前，注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
                //比如 array = [4,6]
                //array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
                //如果high = mid - 1，就会产生错误， 因此high = mid
                right = mid;
            }else{
                //出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]
                //此时最小数字不好判断在mid左边还是右边,这时只好一个一个试 
                right--;
            }
        }
        return array[left];
    }
}

二分查找法最主要的注意点就是边界，一定要注意边界的选取，这直接影响了程序的实现细节。