查找-二分查找Binary Search
相信大家都玩过小时候的猜数字游戏:A想一个100以内的数,大家来猜这个数,谁的次数最少谁就获胜。这大概是我们最早接触二分查找了,二分查找是查找算法中效率比较高而且也比较简单的算法,但是使用上会有一些限制,比如需要查找集合是顺序存储的有序表。
一、简述
二分查找又叫折半查找,需要在顺序存储有序表(随机访问)中进行查找。
它的整体思想比较简单易懂,先与顺序表中间元素进行对比,
- 等于中间元素则查找成功;
- 大于中间则在右边子表以同样的方式查询;
- 小于中间则在左边子表以同样的方式查询;
(注意上面的大于小于等于只是抽象的概念,并非只是数字比较,具体的规则有我们自己定义。)
二、算法实现
1、迭代(非递归)
int binarySearch(int key, int[] array, int low, int high) {
if (array.length == 0 || low < high ||
key > array[high] || key < array[low]) {
return -1;
}
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (key == array[mid]) {
return mid;
} else if (key < array[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
2、递归
一般来说二分用迭代循环就好了,不推荐用递归,递归的空间消耗更大。这里可以加深下递归思想的理解。
int binarySearch(int key, int[] array, int low, int high) {
if (array.length == 0 || low > high ||
key > array[high] || key < array[low]) {
return -1;
}
if (low <= high) {
int mid = (low + high) / 2;
if (key == array[mid]) {
return mid;
} else if (key < array[mid]) {
return binarySearch(key, array, low, mid - 1);
} else {
return binarySearch(key, array, mid + 1, high);
}
}
return -1;
}
三、分析
每次查找的范围减少一半,很明显二分查找的时间复杂度是 O(h)=O(lgn)
二分查找很快,但是限制条件也比较多,光是有序条件就比较麻烦,如果维护有序的代价不小的话,就需要权衡了。