二分查找法
二分查找法又或是折半查找法(Binary search, half-interval search)是一种应用于有序数组中的查找算法，由John William Mauchly首次提出于1946年，但第一个没有bug的二分查找法直至1962年才出现
尽管二分查找的基本思想相对简单，但细节可以令人难以招架 … — 高德纳
基本思想
目的是查找有序数列中的一个元素，比较目标元素与有序数列中心元素的大小，大于该元素则在中心元素右侧部分递归查找，小于该元素则在中心元素左侧部分递归查找
代码实现
//MARK: -无注释纯享版
/// 二分查找
/// - Parameter target: 需要查找的元素
/// - Returns: 如果找到该元素则返回index，未找到则返回-1
func binarySearchA(target: Int) -> Int{
var l: Int = 0
var r: Int = arr.count - 1
while l <= r {
let mid = l + (r - l)/2
if arr[mid] == target{
return mid
}
if target < arr[mid] {
r = mid - 1
}
if target > arr[mid] {
l = mid + 1
}
}
return -1
}
/// 递归实现的二分查找
/// - Parameters:
/// - target: 需要查找的元素
/// - l: 查找范围的左边界
/// - r: 查找范围的右边界
/// - Returns: 如果找到该元素则返回index，未找到则返回-1
func binarySearhByRecursion(target: Int, l: Int, r: Int) -> Int{
if l > r {
return -1
}
let mid = l + (r - l)/2
if arr[mid] == target {
return mid
}
else if target < arr[mid] {
return binarySearhByRecursion(target: target, l: l, r: mid - 1)
}
else {
return binarySearhByRecursion(target: target, l: mid + 1, r: r)
}
}
递归实现与非递归实现思路基本一致，注释版不再赘述
//MARK: -注释版
/// 二分查找
/// - Parameter target: 需要查找的元素
/// - Returns: 如果找到该元素则返回index，未找到则返回1
func binarySearchB(target: Int) -> Int{
//在[l...r]中查找
var l: Int = 0
var r: Int = arr.count - 1
//当 l > r 时说明查找已经结束
while l <= r {
//先取数组中心下标
// let mid = (l + r)/2 的问题在于l与r特别大的情况下可能会产生数据溢出
let mid = l + (r - l)/2
//第一种情况是中心元素正好是目标元素
if arr[mid] == target{
return mid
}
//第二种情况是目标元素小于中心元素，则将右边界缩小到中心元素左边第一位
if target < arr[mid] {
r = mid - 1
}
//第三种情况是目标元素大于中心元素，则将做边界缩小到中心元素右边第一位
if target > arr[mid] {
l = mid + 1
}
}
return -1
}