我正在使用 C 做一個關于二分搜索的問題，但我想知道是否有更有效的方法來實作它。
我的代碼如下：
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l (r - l) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] > x) {
return binarySearch(arr, l, mid - 1, x);
} else {
return binarySearch(arr, mid 1, r, x);
}
} else {
return -1;
}
}
uj5u.com熱心網友回復：
我是不進行相等性比較的二分搜索的支持者，因此每個減少步驟都進行一次比較（當間隔縮小時，您最終會執行一次相等性比較）。
比較相等性的想法是您可以在找到鍵時提前終止搜索。如果在深度 d 處找到密鑰，則需要進行 2d 比較。比較的平均次數是樹平均深度的兩倍，對于完美的樹是 2 Log2(N) - 1（提前終止只保留一次比較）。
這將在沒有等式測驗的情況下與 Log2(N) 進行比較。不算在沒有找到鍵的情況下，樹的整個深度總是被遍歷！測驗平等似乎是一個錯誤的好主意。
uj5u.com熱心網友回復：
二分搜索是在我們的陣列中搜索任何特定值的一種非常有效的方法......尤其是在非常長的陣列中，傳統的線性搜索方法會消耗大量的編譯時間。談論時間復雜度 => 線性搜索 O(n) 而二分搜索有時間復雜度：O(log2n) {log n with base 2}
所以在這個二進制搜索代碼中不需要其他優化，但是是的......你可以學習三元搜索而不是二元搜索，它并不比二元搜索快，但有利于學習新事物...... https://www.geeksforgeeks .org/三元搜索/
三元搜索就像二元搜索一樣，但在這里，將陣列分為 3 部分，然后我們進行比較。三元搜索的時間復雜度也是 O(log3n) :log n with base 3
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/380999.html
上一篇：如何有效地創建子串