查找

二分查找：

二分查找是一个基础的算法，也是面试中常考的一个知识点。二分查找就是将查找的键和数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

如果面试题要求在排序的数组（或者部分排序的数组）中查找数字或者统计某个数字出现的次数，都可以尝试使用二分查找

实现（非递归）：

/**
 * 二分查找，找到该值在数组中的下标，否则为-1
 */
public int binarySerach(int[] array, int key) {
    if (array == null || array.length < 1) {return -1;}
    int left = 0;
    int right = array.length - 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == key) {
            return mid;
        }
        else if (array[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

　　注意：代码中的判断条件必须是while (left <= right)，否则的话判断条件不完整，比如：array[3] = {1, 3, 5};待查找的键为5，此时在(low < high)条件下就会找不到，因为low和high相等时，指向元素5，但是此时条件不成立，没有进入while()中。

递归实现：

public int binarySearch_digui(int[] array,int data,int left,int right){
        int middle = (left + right)/2;
        if (left > right) return -1;
        if (data > array[middle]){
            return binarySearch_digui(array,data,middle+1,right);
        }else if (data < array[middle]){
            return binarySearch_digui(array,data,left,middle-1);
        }else {
            return middle;
        }
    }

时间复杂度：O（logn）

空间复杂度：O（1）

复杂度分析:
因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
一次二分剩下：n/2
两次二分剩下：n/2/2 = n/4
。。。
m次二分剩下：n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为
 n/(2^m)=1;
2^m=n;
所以时间复杂度为：log2(n)