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
// 使用二分搜索算法搜索数组元素的函数
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 {
// 找到关键元素
return middle
} else if arr[middle] < key {
// 在上半部分搜索
LBound = middle + 1
} else {
// 在下半部分搜索
UBound = middle - 1
}
}
// 未找到关键元素
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) 时间复杂度。
