資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Swift 實現二分查詢演算法
在 Swift 中，二分查詢演算法用於在已排序的陣列中搜索元素。它反覆將搜尋區間分成兩半，然後搜尋指定的元素。在二分查詢演算法中，輸入陣列必須按排序順序排列，以減少時間複雜度。
演算法
步驟 1 − 建立一個函式來實現二分查詢演算法。
步驟 2 − 在函式內部，首先我們找到給定陣列的下界和上界範圍。
步驟 3 − 執行一個 while 迴圈，直到 LBound<=UBound。
步驟 4 − 現在找到給定範圍的中值。並檢查中值是否等於關鍵元素。如果是，則返回索引值。
步驟 5 − 檢查關鍵元素是否小於中間索引，如果是，則搜尋上半部分範圍。
步驟 6 − 如果關鍵元素大於中間索引，則搜尋下半部分範圍。
步驟 7 − 如果在給定陣列中找不到關鍵元素，則返回 nil。
步驟 8 − 在函式外部建立一個數組。
步驟 9 − 呼叫函式並將陣列和關鍵元素傳遞給它。
步驟 10 − 列印搜尋元素的索引。
示例
在下面的示例中，我們將建立一個名為 binarySearchAlgo() 的函式。此函式將一個已排序的陣列作為輸入，並查詢給定陣列是否包含指定的陣列。因此，此函式有兩個名為 LBound 和 UBound 的變數來跟蹤搜尋陣列的範圍。然後我們執行一個 while 迴圈，直到 LBound<=UBound。在迴圈內部，我們找到給定範圍的中間索引，然後檢查以下條件 -
如果關鍵元素等於中間元素，則返回中間索引。
如果中間元素小於關鍵元素，則搜尋上半部分範圍。
如果中間元素大於關鍵元素，則搜尋下半部分範圍。
如果在給定陣列中找不到關鍵元素，則返回 nil。
import Foundation
import Glibc
// Function to search an array element using binary search algorithm
func binarySearchAlgo(arr: [Int], key: Int) -> Int? {
var LBound = 0
var UBound = arr.count - 1
while LBound <= UBound {
let middle = (LBound + UBound) / 2
if arr[middle] == key {
// Found the key element
return middle
} else if arr[middle] < key {
// Searching in the upper half
LBound = middle + 1
} else {
// Searching in the lower half
UBound = middle - 1
}
}
// Key element is not found
return nil
}
let arr = [4, 6, 8, 24, 67, 90]
if let indexValue = binarySearchAlgo(arr: arr, key: 24) {
print("Found at index: \(indexValue)")
} else {
print("Not found")
}
輸出
Found at index: 3
結論
因此，這就是我們如何實現二分查詢演算法。二分查詢是最快的搜尋演算法，因為輸入陣列已排序。在本文中，我們使用迭代方法來實現二分查詢演算法，其時間複雜度為 O(log n)。二分查詢演算法對於小陣列和較大陣列都執行良好。二分查詢演算法的主要缺點是它需要一個已排序的陣列。如果陣列未排序，則它會對陣列進行排序，這會增加額外的 O(nlogn) 時間複雜度。
1K+ 瀏覽量
