查找(Searching)，在计算机中是一个比较常用的操作，通常是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或者元素。如果表中存在这样的元素，则称查找成功，否则就表示查找失败。
我们今天要说的查找，是指基于顺序表的查找，而且主要是静态查找(Static Search)，也就是说，在查找过程中不涉及元表中元素的修改。
一、顺序查找(Sequential Search)
顺序查找又称线性查找，是指从表中第一个元素开始，逐步和给定的关键字进行比较，如果顺序表中某个元素和给定的关键字相等，则表示查找成功，否则就表示查找失败。用代码表示为：
// 给定一个顺序表
let numberList = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
/// 查找数组中是否存在某个元素
/// 数组中的元素必须是可以比较
/// 的，为此需要遵守Comparable协议
extension Array where Element: Comparable {
/// 根据给定的元素去数组中查找
/// - 参数key: 内部参数，用于接收从外部传递过来的元素值
/// - returns: 如果找到了，就返回true，否则返回false
func linearSearch(forElement key: Element) -> Bool {
// 遍历数组
for number in self {
if number == key {
return true
}
}
return false
}
}
// 查看搜寻的结果
let isNotFound: Bool = numberList.linearSearch(forElement: 8) // 结果为false
let isFound = numberList.linearSearch(forElement: 88) // 结果为true
顺序查找的效率为O(n)，也就是说，顺序表中的元素越多，它的效率就越低。因此，它只适合表中元素比较少的顺序表，如果表中的元素非常多，我们必须另想办法。
二、折半查找(Binary Search)
当顺序表中的元素比较多时，为了提高查找效率，我们可以使用折半查找。折半查找的工作原理是：先确定顺序表中第一个元素的索引min和最后一个元素的索引max，然后再确定中间元素的索引mid，根据中间元素的索引mid取出中间元素，最后再用这个元素去和给定的关键字进行比较，如果中间元素比给定的关键字大，则说明我们要查找的元素范围在(min, mid - 1)之间，应该继续应用折半查找；如果中间元素比给定的关键字小，则说明我们要查找的元素范围在(mid + 1, max)之间，应该继续应用折半查找；如果中间元素恰好等于给定的关键字，则表示查找成功。用代码表示为：
// 给定一个顺序表
var numberList = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
extension Array where Element: Comparable {
/// Array是一个结构体。结构体的方法在操作过程中，如果对结构体中的元素有所改动，
/// 则必须在方法前面用关键字mutating修饰
mutating func binarySearch(forElement key: Element) -> Bool {
var result = false
// 创建索引
let min = self.startIndex // 开始索引
let max = self.endIndex - 1 // 尾部索引
let mid = self.midIndex() // 中间索引
// 检查边界(大于表中最大元素，或者小于表中最小元素)
if key > self[max] || key < self[min] {
// 要查找的元素不在表中
print("元素\(key)没有找到")
return false
}
// 取出表中中间的元素
let n = self[mid]
// 如果中间元素的值大于关键字key
if n > key {
// 当表中中间元素比关键字大时，则表示要查找的元素
// 应该在索引为min到mid - 1这个范围之内
var slice = Array(self[...(mid - 1)]) // 在Swift 3中的写法：var slice = Array(self[min...mid - 1])
// 继续对数组slice执行折半查找
result = slice.binarySearch(forElement: key) }
// 如果中间元素的值小于关键字key
else if n < key {
// 当表中中间元素比关键字小时，则表示要查找的元素
// 应该在索引为mid + 1到max这个范围之内
var slice = Array(self[(mid + 1)...]) // 在Swift 3中的写法：var slice = Array(self[mid + 1...max])
// 继续对数组slice执行折半查找
result = slice.binarySearch(forElement: key) }
else {
// 则表示查找到关键字
print("在顺序表中找到符合要求的元素\(key)")
result = true
}
// 将结果进行返回
return result
}
/// 返回中间的索引
func midIndex() -> Index { return startIndex + (count / 2) }
}
// 执行查找
let isFound: Bool = numberList.binarySearch(forElement: 88)
折半查找的效率是O(logn)，比顺序查找的效率高，但是折半查找只适用于顺序存储结构的有序表，对线性链表无法应用折半查找。
