算法：二分搜索算法（折半查找算法）
時間復雜度：
- 二分搜索算法概述
- 二分搜索算法偽代碼
- 二分搜索算法實現(xiàn)
二分搜索算法概述
二分搜索算法即彪，也稱折半查找算法，即在一個有序數(shù)組中查找某一個特定元素。整個搜索過程從中間開始轻庆，如果要查找的元素即中間元素攘蔽，那么搜索過程結束；反之根據(jù)中間元素與要查找元素的關系在數(shù)組對應的那一半查找，例如查找元素大于中間元素枢步，則在整個數(shù)組較大元素的那一半查找砖茸，反復進行這個過程，直到找到元素，或者數(shù)組為空蹲姐，查找不到元素顷扩。
二分搜索算法描述
給定一個數(shù)組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 實現(xiàn)
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
遞歸實現(xiàn)
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
二分查找算法實現(xiàn)
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;
參考資料
- 《數(shù)據(jù)結構基礎（C語言版）》第二版
- 二分搜索算法 - 維基百科抵栈，自由的百科全書
本文首發(fā)于個人博客算法 - 二分搜索算法 | 不存在的貓， 轉載請注明出處
