算法：二分搜索算法（折半查找算法）
时间复杂度：
- 二分搜索算法概述
- 二分搜索算法伪代码
- 二分搜索算法实现
二分搜索算法概述
二分搜索算法，也称折半查找算法，即在一个有序数组中查找某一个特定元素。整个搜索过程从中间开始，如果要查找的元素即中间元素，那么搜索过程结束；反之根据中间元素与要查找元素的关系在数组对应的那一半查找，例如查找元素大于中间元素，则在整个数组较大元素的那一半查找，反复进行这个过程，直到找到元素，或者数组为空，查找不到元素。
二分搜索算法描述
给定一个数组A_0,A_1...A_{n-1}， A_0 \le A_1 \le \cdot \le A_{n - 1}，待查找元素为searchnum：
- 用
left，right分别表示左右端点，即要查找的范围； - 用
middle表示中间点，middle = \lfloor (left + right) / 2 \rfloor； - 若
left > right，搜索失败； - 若
A{middle} > searchnum，right = middle - 1，返回3； - 若
A{middle} < searchnum，left = middle + 1，返回3； - 若
A{middle} = searchnum，搜索结束，返回middle。
二分搜索算法伪代码
while 实现
BINARY-SEARCH-WHILE(A, searchnum, left, right)
while left <= right
middle = (left + right) div 2
case
A_middle < searchnum : left = middle + 1
A_middle > searchnum : right = middle - 1
A_middle = searchnum : return middle
return FAILED
递归实现
BINARY-SEARCH-RECURSION(A, searchnum, left, right)
if left <= right
middle = (left + right) div 2
case
A_middle < searchnum :
return (A, searchnum, middle + 1, right)
A_middle > searchnum :
return (A, searchnum, left, middle - 1)
A_middle = searchnum :
return middle
二分查找算法实现
C
while 版本
int binarySearch(arrType * a, arrType searchnum, int left, int right)
{
int middle;
while (left <= right) {
middle = (left + right) / 2;
if (a[middle] > searchnum)
right = middle - 1;
else if (a[middle] < searchnum)
left = middle + 1;
else if (a[middle] == searchnum)
return middle;
}
return -1;
}
递归版本
int binarySearch(arrType * a, arrType searchnum, int left, int right)
{
int middle;
if (left <= right) {
middle = (left + right) / 2;
if (a[middle] > searchnum)
return binarySearch(a, searchnum, left, middle - 1);
else if (a[middle] < searchnum)
return binarySearch(a, searchnum, middle + 1, right);
else if (a[middle] == searchnum)
return middle;
}
return -1;
}
Pascal
外部定义全局变量：
var
a : array[1..n] of integer;
searchnum, result :integer;
while 版本
procedure binarySearch(left, right :integer);
var
middle : integer;
begin
while (left <= right) do
begin
middle := (left + right) div 2;
if (a[middle] > searchnum) then
right := middle - 1
else if (a[middle] < searchnum) then
left := middle + 1
else
begin
result := middle;
break;
end;
end;
if left > right then
result := -1;
end;
递归版本
procedure binarySearch(left, right :integer);
var
middle : integer;
begin
if left <= right then
begin
middle := (left + right) div 2;
if (a[middle] > searchnum) then
binarySearch(left, middle - 1)
else if (a[middle] < searchnum) then
binarySearch(middle + 1, right)
else
result := middle;
end
else
result := -1;
end;
参考资料
- 《数据结构基础（C语言版）》第二版
- 二分搜索算法 - 维基百科，自由的百科全书
本文首发于个人博客算法 - 二分搜索算法 | 不存在的貓， 转载请注明出处
