二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，前提是数据结构必须先排好序，可以在数据规模的对数时间复杂度内完成查找。但是，二分查找要求线性表具有有随机访问的特点（例如数组），也要求线性表能够根据中间元素的特点推测它两侧元素的性质，以达到缩减问题规模的效果。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

//不使用递归实现（while循环）
/**
 * 二分查找，找到该值在数组中的下标，否则返回-1
 */
static int binarySerach(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    
    if(key < arr[low] || key > arr[high] || low > high){
			return -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;
}

//递归实现
public static int recursionBinarySearch(int[] arr,int key,int low,int high){
		
		if(key < arr[low] || key > arr[high] || low > high){
			return -1;				
		}
		
		int middle = (low + high) / 2;			//初始中间位置
		if(arr[middle] > key){
			//比关键字大则关键字在左区域
			return recursionBinarySearch(arr, key, low, middle - 1);
		}else if(arr[middle] < key){
			//比关键字小则关键字在右区域
			return recursionBinarySearch(arr, key, middle + 1, high);
		}else {
			return middle;
		}	
		
	}

二分查找总结

// 这里必须是 <=
while (left <= right) {
    int mid = (left + right) / 2;
    if (array[mid] ? key) {//2.判断出比较符号
        //... right = mid - 1;
    }
    else {
        // ... left = mid + 1;
    }
}
return xxx;//1.首先判断返回left，还是right

时间复杂度

采用的是分治策略

最坏的情况下两种方式时间复杂度一样：O(log2N)

最好情况下为：O(1)

空间复杂度

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数

非递归方式：
由于辅助空间是常数级别的，所以：
空间复杂度是O(1);

递归方式：

递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的，所以：
空间复杂度：O(log2N )