数据结构
网络
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+ 浏览量
