Loading AI tools
搜索算法 来自维基百科，自由的百科全书
在電腦科學中，二分搜尋演算法（英語：binary search algorithm），也稱折半搜尋演算法（英語：half-interval search algorithm）[1]、對數搜尋演算法（英語：logarithmic search algorithm）[2]，是一種在有序陣列中搜尋某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始，如果中間元素正好是要搜尋的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中搜尋，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
二分搜尋演算法在最壞情況下是對數時間複雜度的，需要進行次比較操作（在此處是陣列的元素數量，是大O記號，是對數）。二分搜尋演算法使用常數空間，對於任何大小的輸入數據，演算法使用的空間都是一樣的。除非輸入數據數量很少，否則二分搜尋演算法比線性搜尋更快，但陣列必須事先被排序。儘管一些特定的、為了快速搜尋而設計的數據結構更有效（比如雜湊表），二分搜尋演算法應用面更廣。
二分搜尋演算法有許多種變種。比如分散層疊可以提升在多個陣列中對同一個數值的搜尋的速度。分散層疊有效的解決了計算幾何學和其他領域的許多搜尋問題。指數搜尋將二分搜尋演算法拓寬到無邊界的列表。二叉搜尋樹和B樹數據結構就是基於二分搜尋演算法的。
二分搜尋只對有序陣列有效。二分搜尋先比較陣列中位元素和目標值。如果目標值與中位元素相等，則返回其在陣列中的位置；如果目標值小於中位元素，則搜尋繼續在前半部分的陣列中進行。如果目標值大於中位元素，則搜尋繼續在陣列上部分進行。由此，演算法每次排除掉至少一半的待查陣列。
給予一個包含個帶值元素的陣列或是記錄，使，以及目標值，還有下列用來搜尋在中位置的子程式[3]。
這個疊代步驟會持續透過兩個變數追蹤搜尋的邊界。有些實際應用會在演算法的最後放入相等比較，讓比較迴圈更快，但平均而言會多一層疊代[4]。
以上程式只適用於完全匹配，也就是尋找一個目標值的位置。不過，因為有序陣列的順序性，將二分搜尋演算法擴展到能適用大致匹配並不是很重要。舉例來說，二分搜尋演算法可以用來計算一個賦值的排名（或稱秩，比它更小的元素的數量）、前趨（下一個最小元素）、後繼（下一個最大元素）以及最近鄰。搜尋兩個值之間的元素數目的範圍查詢可以藉由兩個排名查詢（又稱秩查詢）來執行[5]。
除直接在一個陣列中搜尋元素外，可用在插入排序中。
 |
int binary_search(const int arr[], int start, int end, int key) {
if (start > end)
return -1;
int mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
if (arr[mid] > key)
return binary_search(arr, start, mid - 1, key);
else if (arr[mid] < key)
return binary_search(arr, mid + 1, end, key);
else
return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}
int binary_search(const int arr[], int start, int end, int key) {
int ret = -1; // 未搜索到数据返回-1下标
int mid;
while (start <= end) {
mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
if (arr[mid] < key)
start = mid + 1;
else if (arr[mid] > key)
end = mid - 1;
else { // 最後檢測相等是因為多數搜尋狀況不是大於要不就小於
ret = mid;
break;
}
}
return ret; // 单一出口
}
var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15, 19, 20];
const binarySearch = (arr, target) => {
const search = (start, end) => {
if (start > end) return -1;
const mid = start + Math.floor((end - start) / 2);
if (arr[mid] > target) {
return search(0, mid - 1);
} else if (arr[mid] < target) {
return search(mid + 1, end);
} else {
return mid;
}
}
return search(0, arr.length - 1);
}
console.log( binarySearch(arr, 4) );
def binary_search(arr, left, right, key):
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
left = mid + 1
elif arr[mid] > key:
right = mid - 1
return -1
def binary_search(arr, start, end, key):
if start > end:
return -1
mid = start + (end - start) // 2
if arr[mid] > key:
return binary_search(arr, start, mid - 1, key)
if arr[mid] < key:
return binary_search(arr, mid + 1, end, key)
return mid
static int binary_search(int[] arr, int start, int end, int key)
{
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (arr[mid] < key)
start = mid + 1;
else if (arr[mid] > key)
end = mid - 1;
else
return mid;
}
return -1;
}
import Foundation
/// 二分搜索完全匹配
///
/// - Parameters:
/// - arr: 有序数组
/// - start: 起始位置
/// - end: 结束点
/// - key: 特点目标值
/// - Returns: 返回查找结果
func binarySearch(arr: [Int], start: Int, end: Int, key: Int) -> Int? {
if start > end {
return nil
}
let mid = start + (end - start) / 2
if arr[mid] > key {
return binarySearch(arr: arr, start: start, end: mid - 1, key: key)
} else if arr[mid] < key {
return binarySearch(arr: arr, start: mid + 1, end: end, key: key)
} else {
return mid
}
}
func binary_search(arr []int, low, high, key int) int {
if low > high {
return -1
}
mid := low + (high-low)/2
if arr[mid] > key {
return binary_search(arr, low, mid-1, key)
} else if arr[mid] < key {
return binary_search(arr, mid+1, high, key)
}
return mid
}
func binarySearch(arr []int, key int) int {
low, high := 0, len(arr)-1
for low <= high {
mid := low + (high-low)/2
if arr[mid] == key {
return mid
} else if key < arr[mid] {
high = mid - 1
} else if key > arr[mid] {
low = mid + 1
}
}
return -1
}
public static int binarySearch(int[] arr, int start, int end, int key){
if (start > end)
return -1;
int mid = start + (end - start)/2; //防止溢位
if (arr[mid] > key)
return binarySearch(arr, start, mid - 1, key);
if (arr[mid] < key)
return binarySearch(arr, mid + 1, end, key);
return mid;
}
public static int binarySearch(int[] arr, int start, int end, int key){
int result = -1;
while (start <= end){
int mid = start + (end - start)/2; //防止溢位
if (arr[mid] > key)
end = mid - 1;
else if (arr[mid] < key)
start = mid + 1;
else {
result = mid ;
break;
}
}
return result;
}
# Julia Sample : BinarySearch
function BinarySearch(A,Key)
left,right = 1,length(A)
while(left<=right)
mid=left+floor(Int,((right-left)/2))
if A[mid]==Key
return mid
elseif Key<A[mid]
right = mid-1
elseif Key>A[mid]
left = mid+1
end
end
return -1
end
# Main Code
A = [1,3,16,31,43,354,586] # Already Arrange
println(A) # Original Array
println(BinarySearch(A,43)) # BinarySearch Search Array
println(BinarySearch(A,354)) # BinarySearch Search Array
println(BinarySearch(A,3)) # BinarySearch Search Array
在1946年，約翰·莫奇利在摩爾學院講座上第一次提出二分搜尋的概念。[8]1957年，威廉·皮特遜發表了第一個應用插值搜尋的演算法[8][9]。在此時，每個發表的二分搜尋演算法只對長度為2的冪減一的陣列有用。[10]直到1960年，德里克·亨利·萊默發表了一個對於所有長度的陣列都適用的演算法[11]。1962年，赫爾曼·博滕布魯赫發表了一個用ALGOL 60寫的二分搜尋，將判斷相等的步驟放到演算法末尾。雖然將平均疊代次數增加一，但是每次疊代中的比較次數減少了1次。[12]均勻二分搜尋則是史丹福大學的A. K.錢德拉在1971年發明的[8]。1986年，伯納德·查澤爾和列奧尼達斯·吉巴斯引入了分散層疊來解決計算幾何中大量存在的搜尋問題[13][14][15]。
當喬恩·本特利將二分搜尋問題佈置給專業編程課的學生時，百分之90的學生在花費數小時後還是無法給出正確的解答，主要因為這些錯誤程式在面對邊界值的時候無法執行，或返回錯誤結果。[16]1988年開展的一項研究顯示，20本教科書裏只有5本正確實現了二分搜尋。[17]不僅如此，本特利自己1986年出版的《編程珠璣》一書中的二分搜尋演算法存在整數溢位的問題，二十多年來無人發現。Java語言的庫所實現的二分搜尋演算法中同樣的溢位問題存在了九年多才被修復。[18]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
