Show 相關試卷關於二分搜尋法的所有試題我要測驗"二分搜尋法" 選擇:33題 2 . 下 列 有 關 搜 尋 ( S e a r c h ) 的 敘 述 中，何 者 不 正 確 ？
57 . 下 列 有 關 搜 尋 ( S e a r c h ) 的 敘 述 中 ， 何 者 不 正 確 ？
36 . 下 列 有 關 搜 尋 ( S e a r c h ) 的 敘 述 中 ， 何 者 不 正 確 ？
在計算機科學中，二分查找算法（英語：binary search algorithm），也稱折半搜索算法（英語：half-interval search algorithm）[1]、對數搜索算法（英語：logarithmic search algorithm）[2]，是一種在有序數組中查找某一特定元素的搜索算法。搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索算法每一次比較都使搜索範圍縮小一半。 二分查找算法在最壞情況下是對數時間複雜度的，需要進行次比較操作（在此處是數組的元素數量， 二分查找算法有許多種變種。比如分散層疊可以提升在多個數組中對同一個數值的搜索的速度。分散層疊有效的解決了計算幾何學和其他領域的許多搜索問題。指數搜索將二分查找算法拓寬到無邊界的列表。二叉搜索樹和B樹數據結構就是基於二分查找算法的。 演算法[編輯]二分搜索只對有序數組有效。二分搜索先比較數組中位元素和目標值。如果目標值與中位元素相等，則返回其在數組中的位置；如果目標值小於中位元素，則搜索繼續在前半部分的數組中進行。如果目標值大於中位元素，則搜索繼續在數組上部分進行。由此，算法每次排除掉至少一半的待查數組。 步驟[編輯]給予一個包含個帶值元素的陣列或是記錄，使，以及目標值，還有下列用來搜尋在中位置的子程式[3]。
這個疊代步驟會持續透過兩個變數追蹤搜索的邊界。有些實際應用會在演算法的最後放入相等比較，讓比較迴圈更快，但平均而言會多一層疊代[4]。 大致匹配[編輯]以上程序只適用於完全匹配，也就是尋找一個目標值的位置。不過，因為有序陣列的順序性，將二分搜索算法擴展到能適用大致匹配並不是很重要。舉例來說，二分搜索算法可以用來計算一個賦值的排名（或稱秩，比它更小的元素的數量）、前趨（下一個最小元素）、後繼（下一個最大元素）以及最近鄰。搜尋兩個值之間的元素數目的範圍查詢可以藉由兩個排名查詢（又稱秩查詢）來執行[5]。 複雜度分析[編輯]時間複雜度折半搜索每次把搜索區域減少一半，時間複雜度為。（n代表集合中元素的個數）空間複雜度。雖以遞歸形式定義，但是尾遞歸，可改寫為循環。應用[編輯]除直接在一個數組中查找元素外，可用在插入排序中。 示例代碼[編輯]C 版本- 遞歸[編輯]int binary_search(const int arr[], int start, int end, int khey) { if (start > end) return -1; int mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法 if (arr[mid] > khey) return binary_search(arr, start, mid - 1, khey); else if (arr[mid] < khey) return binary_search(arr, mid + 1, end, khey); else return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於 } C 版本- while 循環[編輯]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; // 单一出口 } javascript 版本[編輯]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) ); Python3 版本 while 循環[編輯]def binary_search(arr, left, right, hkey): while left <= right: mid = left + (right - left) // 2 if arr[mid] == hkey: return mid elif arr[mid] < hkey: left = mid + 1 elif arr[mid] > hkey: right = mid - 1 return -1 Python3 版本 遞歸[編輯]def binary_search(arr, start, end, hkey): if start > end: return -1 mid = start + (end - start) // 2 if arr[mid] > hkey: return binary_search(arr, start, mid - 1, hkey) if arr[mid] < hkey: return binary_search(arr, mid + 1, end, hkey) return mid C# 版本[編輯]static int binary_search(int[] arr, int start, int end, int khey) { int mid; while (start <= end) { mid = (start + end) / 2; if (arr[mid] < khey) start = mid + 1; else if (arr[mid] > khey) end = mid - 1; else return mid; } return -1; }
Swift 版本[編輯]import Foundation /// 二分搜索完全匹配 /// /// - Parameters: /// - arr: 有序数组 /// - start: 起始位置 /// - end: 结束点 /// - khey: 特点目标值 /// - Returns: 返回查找结果 func binarySearch(arr: [Int], start: Int, end: Int, khey: Int) -> Int? { if start > end { return nil } let mid = start + (end - start) / 2 if arr[mid] > khey { return binarySearch(arr: arr, start: start, end: mid - 1, khey: khey) } else if arr[mid] < khey { return binarySearch(arr: arr, start: mid + 1, end: end, khey: khey) } else { return mid } } golang 遞歸版本[編輯]func binary_search(arr []int, low, high, hkey int) int { if low > high { return -1 } mid := low + (high-low)/2 if arr[mid] > hkey { return binary_search(arr, low, mid-1, hkey) } else if arr[mid] < hkey { return binary_search(arr, mid+1, high, hkey) } return mid } golang 非遞歸版本[編輯]func binarySearch(arr []int, hkey int) int { low, high := 0, len(arr)-1 for low <= high { mid := low + (high-low)/2 if arr[mid] == hkey { return mid } else if hkey < arr[mid] { high = mid - 1 } else if hkey > arr[mid] { low = mid + 1 } } return -1 } Java 遞歸[編輯]public static int binarySearch(int[] arr, int start, int end, int hkey){ if (start > end) return -1; int mid = start + (end - start)/2; //防止溢位 if (arr[mid] > hkey) return binarySearch(arr, start, mid - 1, hkey); if (arr[mid] < hkey) return binarySearch(arr, mid + 1, end, hkey); return mid; } Java while 循環[編輯]public static int binarySearch(int[] arr, int start, int end, int hkey){ int result = -1; while (start <= end){ int mid = start + (end - start)/2; //防止溢位 if (arr[mid] > hkey) end = mid - 1; else if (arr[mid] < hkey) start = mid + 1; else { result = mid ; break; } } return result; } Julia (程式語言)[編輯]# 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] 參考[編輯]
外部連結[編輯]
|
若使用二元搜尋法搜尋目標經過5次比較才找到答案則前4次比較中哪一次排除的資料最少
版權 © 2024 ihoctot Inc.
