傻妞也
二分查找又称折半查找，是一种基于分治思想的快速搜索算法，时间复杂度为o(logn)。
二分查找算法只适用于有序序列，换句话说，只有保证序列有序的情况下，才能使用二分查找算法。
二分查找算法的基本原理
以在升序序列中查找目标元素为例，二分查找算法的搜索过程是：找到搜索区域内的中间元素，和目标元素进行比对：
如果相等，则成功找到目标元素，返回该元素所在的位置；
如果目标元素的值大于中间元素，表明目标元素位于中间元素的右侧，因此以中间元素的右侧区域作为新的搜索区域，继续以同样的方法查找目标元素；
如果目标元素的值小于中间元素，表明目标元素位于中间元素的左侧，因此以中间元素的左侧区域作为新的搜索区域，继续以同样的方法查找目标元素；
举个例子，在下图所示的序列中，使用二分查找算法搜索元素 31 的过程是：
1) 找到搜索区域内的中间元素，可以使用如下公式求得中间元素的位置：
mid = ? low (high - low) / 2 ?
其中，low 表示搜索区域第一个元素所在位置的下标，high 表示搜索区域最后一个元素所在位置的下标。
图 1 中，搜索区域为整个序列，中间元素的位置为 ?0 (9-0)/2?= 4，如下图所示（箭头指向的元素为中间元素）：
2) 由于 27< 31，因此搜索区域更新为元素 27 的右侧区域，如下图所示：
重复执行第 1 步，搜索区域内的中间元素下标为 ?5 (9-5)/2? = 7，因此新的中间元素是 35，如下图所示：
3) 由于 35>31，因此搜索区域再次更新为元素 35 左侧的区域，如图 5 所示：
重复执行第 1 步，搜索区域内的中间元素下标为 ?5 (6-5)/2? = 5，因此新的中间元素为 31，和目标元素相等，所以查找成功。
二分查找算法的具体实现
如下为实现二分查找算法的伪代码：
输入 arr[] // 输入有序序列
binary_search( arr , p , q , ele): // [p,q] 指定搜索区域，ele 为要搜索的目标元素
if p > q: // [p,q] 不存在时，返回一个错误值（比如 -1）
return -1
mid <- ?p (q-p)/2? // 找到 [p,q] 区域内中间元素所在位置的下标
if ele == arr[mid]: // 递归的出口，即 ele 和中间元素的值相等
return mid
if ele ＜ arr[mid]: // 比较 ele 和中间元素的值，进一步缩小搜索区域
return binary_search(arr , p , mid-1 , ele)
else:
return binary_search(arr , mid 1 , q , ele)
如下为实现二分查找算法的 c 语言程序：
#include//实现二分查找算法，ele 表示要查找的目标元素，[p,q] 指定查找区域 int binary_search(int *arr,int p,int q,int ele) { int mid = 0; //如果[p,q] 不存在，返回 -1 if (p > q) { return -1; } // 找到中间元素所在的位置 mid = p (q - p) / 2; //递归的出口 if (ele == arr[mid]) { return mid; } //比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域 if (ele < arr[mid]) { //新的搜索区域为 [p,mid-1] return binary_search(arr, p, mid - 1, ele); } else { //新的搜索区域为 [mid 1,q] return binary_search(arr, mid 1, q, ele); } } int main() { int arr[10] = { 10,14,19,26,27,31,33,35,42,44 }; //输出二叉查找元素 31 所在位置的下标 printf("%d", binary_search(arr, 0, 9, 31)); return 0; }
如下为实现二分查找算法的 java 程序：
public class demo {
// 实现二分查找算法，ele 表示要查找的目标元素，[p,q] 指定查找区域
public static int binary_search(int[] arr, int p, int q, int ele) {
// 如果[p,q] 不存在，返回 -1
if (p > q) {
return -1;
}
// 找到中间元素所在的位置
int mid = p (q - p) / 2;
// 递归的出口
if (ele == arr[mid]) {
return mid;
}
// 比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域
if (ele < arr[mid]) {
// 新的搜索区域为 [p,mid-1]
return binary_search(arr, p, mid - 1, ele);
} else {
// 新的搜索区域为 [mid 1,q]
return binary_search(arr, mid 1, q, ele);
}
}
public static void main(string[] args) {
int[] arr = new int[] { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44 };
// 输出二叉查找元素 31 所在位置的下标
int add = binary_search(arr, 0, 9, 31);
system.out.print(add);
}
}
如下为实现二分查找算法的 python 程序：
格式化复制
#实现二分查找算法，ele 表示要查找的目标元素，[p,q] 指定查找区域 def binary_search(arr,p,q,ele): #如果[p,q] 不存在，返回 -1 if p > q: return -1 #找到中间元素所在的位置 mid = p int( (q - p) / 2 ) #递归的出口 if ele == arr[mid]: return mid #比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域 if ele < arr[mid]: return binary_search(arr,p,mid-1,ele) else: return binary_search(arr,mid 1,q,ele) arr = [10, 14, 19, 26, 27, 31, 33, 35, 42, 44] #输出二叉查找元素 31 所在位置的下标 add = binary_search(arr, 0, 9, 31); print(add)
以上程序的输出结果均为：
5
