??查找(Searching)拌夏，在計(jì)算機(jī)中是一個(gè)比較常用的操作稚新，通常是指根據(jù)給定的某個(gè)值盆顾，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的記錄或者元素诬像。如果表中存在這樣的元素屋群，則稱查找成功，否則就表示查找失敗坏挠。
??我們今天要說的查找芍躏，是指基于順序表的查找，而且主要是靜態(tài)查找(Static Search)癞揉，也就是說纸肉，在查找過程中不涉及元表中元素的修改溺欧。
一喊熟、順序查找(Sequential Search)
??順序查找又稱線性查找，是指從表中第一個(gè)元素開始姐刁，逐步和給定的關(guān)鍵字進(jìn)行比較芥牌，如果順序表中某個(gè)元素和給定的關(guān)鍵字相等，則表示查找成功聂使，否則就表示查找失敗壁拉。用代碼表示為：
// 給定一個(gè)順序表
let numberList = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
/// 查找數(shù)組中是否存在某個(gè)元素
/// 數(shù)組中的元素必須是可以比較
/// 的，為此需要遵守Comparable協(xié)議
extension Array where Element: Comparable {
/// 根據(jù)給定的元素去數(shù)組中查找
/// - 參數(shù)key: 內(nèi)部參數(shù)柏靶，用于接收從外部傳遞過來的元素值
/// - returns: 如果找到了弃理，就返回true，否則返回false
func linearSearch(forElement key: Element) -> Bool {
// 遍歷數(shù)組
for number in self {
if number == key {
return true
}
}
return false
}
}
// 查看搜尋的結(jié)果
let isNotFound: Bool = numberList.linearSearch(forElement: 8) // 結(jié)果為false
let isFound = numberList.linearSearch(forElement: 88) // 結(jié)果為true
??順序查找的效率為O(n)屎蜓，也就是說痘昌，順序表中的元素越多，它的效率就越低炬转。因此辆苔，它只適合表中元素比較少的順序表，如果表中的元素非常多扼劈，我們必須另想辦法驻啤。
二、折半查找(Binary Search)
??當(dāng)順序表中的元素比較多時(shí)荐吵，為了提高查找效率骑冗，我們可以使用折半查找赊瞬。折半查找的工作原理是：先確定順序表中第一個(gè)元素的索引min和最后一個(gè)元素的索引max，然后再確定中間元素的索引mid贼涩，根據(jù)中間元素的索引mid取出中間元素森逮，最后再用這個(gè)元素去和給定的關(guān)鍵字進(jìn)行比較，如果中間元素比給定的關(guān)鍵字大磁携，則說明我們要查找的元素范圍在(min, mid - 1)之間褒侧，應(yīng)該繼續(xù)應(yīng)用折半查找；如果中間元素比給定的關(guān)鍵字小谊迄，則說明我們要查找的元素范圍在(mid + 1, max)之間闷供，應(yīng)該繼續(xù)應(yīng)用折半查找；如果中間元素恰好等于給定的關(guān)鍵字统诺，則表示查找成功歪脏。用代碼表示為：
// 給定一個(gè)順序表
var numberList = [5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92]
extension Array where Element: Comparable {
/// Array是一個(gè)結(jié)構(gòu)體。結(jié)構(gòu)體的方法在操作過程中粮呢，如果對(duì)結(jié)構(gòu)體中的元素有所改動(dòng)婿失，
/// 則必須在方法前面用關(guān)鍵字mutating修飾
mutating func binarySearch(forElement key: Element) -> Bool {
var result = false
// 創(chuàng)建索引
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]
// 如果中間元素的值大于關(guān)鍵字key
if n > key {
// 當(dāng)表中中間元素比關(guān)鍵字大時(shí)啄寡，則表示要查找的元素
// 應(yīng)該在索引為min到mid - 1這個(gè)范圍之內(nèi)
var slice = Array(self[...(mid - 1)]) // 在Swift 3中的寫法：var slice = Array(self[min...mid - 1])
// 繼續(xù)對(duì)數(shù)組slice執(zhí)行折半查找
result = slice.binarySearch(forElement: key) }
// 如果中間元素的值小于關(guān)鍵字key
else if n < key {
// 當(dāng)表中中間元素比關(guān)鍵字小時(shí)豪硅，則表示要查找的元素
// 應(yīng)該在索引為mid + 1到max這個(gè)范圍之內(nèi)
var slice = Array(self[(mid + 1)...]) // 在Swift 3中的寫法：var slice = Array(self[mid + 1...max])
// 繼續(xù)對(duì)數(shù)組slice執(zhí)行折半查找
result = slice.binarySearch(forElement: key) }
else {
// 則表示查找到關(guān)鍵字
print("在順序表中找到符合要求的元素\(key)")
result = true
}
// 將結(jié)果進(jìn)行返回
return result
}
/// 返回中間的索引
func midIndex() -> Index { return startIndex + (count / 2) }
}
// 執(zhí)行查找
let isFound: Bool = numberList.binarySearch(forElement: 88)
??折半查找的效率是O(logn)，比順序查找的效率高挺物，但是折半查找只適用于順序存儲(chǔ)結(jié)構(gòu)的有序表懒浮，對(duì)線性鏈表無法應(yīng)用折半查找。
