二分查找

二分查找
概况
类别	搜索算法
数据结构	数组
复杂度
平均时间复杂度	$O(\log n)$
最坏时间复杂度	$O(\log n)$
最优时间复杂度	$O(1)$
空间复杂度	迭代：$O(1)$ 递归：$O(\log n)$ （无尾调用消除）
最佳解	Yes
相关变量的定义

在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）、对数搜索算法（英语：logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找算法在最坏情况下是对数时间复杂度的，需要进行$O(\log n)$次比较操作（$n$在此处是数组的元素数量，$O$是大O记号，$\log$是对数）。二分查找算法使用常数空间，对于任何大小的输入数据，算法使用的空间都是一样的。除非输入数据数量很少，否则二分查找算法比线性搜索更快，但数组必须事先被排序。尽管一些特定的、为了快速搜索而设计的数据结构更有效（比如哈希表），二分查找算法应用面更广。

二分查找算法有许多种变种。比如分散层叠可以提升在多个数组中对同一个数值的搜索的速度。分散层叠有效的解决了计算几何学和其他领域的许多搜索问题。指数搜索将二分查找算法拓宽到无边界的列表。二叉搜索树和B树数据结构就是基于二分查找算法的。

算法

二分搜索只对有序数组有效。二分搜索先比较数组中位元素和目标值。如果目标值与中位元素相等，则返回其在数组中的位置；如果目标值小于中位元素，则搜索继续在前半部分的数组中进行。如果目标值大于中位元素，则搜索继续在数组上部分进行。由此，算法每次排除掉至少一半的待查数组。

步骤

给予一个包含$n$个带值元素的数组$A$或是记录$A_{0},\cdots ,A_{n-1}$，使$A_{0}\leq \cdots \leq A_{n-1}$，以及目标值$T$，还有下列用来查找$T$在$A$中位置的子程序。

1. 令$L$为$0$，$R$为$n-1$。
2. 如果$L>R$，则查找以失败告终。
3. 令$m$（中间值元素）为$\lfloor (L+R)/2\rfloor$。（具体实现中，为防止算术溢出，一般采用$\lfloor L+(R-L)/2\rfloor$代替。）
4. 如果$A_{m}<T$，令$L$为$m+1$并回到步骤二。
5. 如果$A_{m}>T$，令$R$为$m-1$并回到步骤二。
6. 当$A_{m}=T$，查找结束；回传值$m$。

这个迭代步骤会持续透过两个变量追踪搜索的边界。有些实际应用会在算法的最后放入相等比较，让比较循环更快，但平均而言会多一层迭代。

大致匹配

以上程序只适用于完全匹配，也就是查找一个目标值的位置。不过，因为有序数组的顺序性，将二分搜索算法扩展到能适用大致匹配并不是很重要。举例来说，二分搜索算法可以用来计算一个赋值的排名（或称秩，比它更小的元素的数量）、前趋（下一个最小元素）、后继（下一个最大元素）以及最近邻。查找两个值之间的元素数目的范围查询可以借由两个排名查询（又称秩查询）来执行。

• 排名查询可以使用调整版的二分搜索来执行。借由在成功的搜索回传$m$，以及在失败的搜索回传$L$，就会取而代之地回传了比起目标值小的元素数目。
• 前趋和后继查询可以借由排名查询来执行。一旦知道目标值的排名，其前趋就会是那个位于其排名位置的元素,或者排名位置的上一个元素（因为它是小于目标值的最大元素）。其后继是（数组中的）下一个元素，或是（非数组中的）前趋的下一个元素。目标值的最近邻可能是前趋或后继，取决于何者较为接近。
• 范围查询也是直接了当的。一旦知道两个值的排名，不小于第一个值且小于第二个值的元素数量就会是两者排名的差。这个值可以根据范围的端点是否算在范围内，或是数组是否包含其端点的对应键来增加或减少1。

复杂度分析

时间复杂度

折半搜索每次把搜索区域减少一半，时间复杂度为$O\left(\log n\right)$。（n代表集合中元素的个数）

空间复杂度

$O\left(1\right)$。虽以递归形式定义，但是尾递归，可改写为循环。

应用

除直接在一个数组中查找元素外，可用在插入排序中。

示例代码

C 版本- 递归

int binary_search(const int arr[], int start, int end, int key) {
	if (start > end)
		return -1;

	int mid = start + (end - start) / 2;    //直接平均可能會溢位，所以用此算法
	if (arr[mid] > key)
		return binary_search(arr, start, mid - 1, key);
	else if (arr[mid] < key)
		return binary_search(arr, mid + 1, end, key);
	else
	    return mid;        //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}

C 版本- while 循环

int binary_search(const int arr[], int start, int end, int key) {
    int ret = -1;       // 未搜索到数据返回-1下标
    
	int mid;
	while (start <= end) {
		mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
		if (arr[mid] < key)
			start = mid + 1;
		else if (arr[mid] > key)
			end = mid - 1;
		else {            // 最後檢測相等是因為多數搜尋狀況不是大於要不就小於
			ret = mid;  
            break;
        }
	}
	
	return ret;     // 单一出口
}

JavaScript 版本

var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15, 19, 20];
const binarySearch = (arr, target) => {
  const search = (start, end) => {
    if (start > end) return -1;
    const mid = start + Math.floor((end - start) / 2);
    if (arr[mid] > target) {
      return search(0, mid - 1);
    } else if (arr[mid] < target) {
      return search(mid + 1, end);
    } else {
      return mid;
    }
  }
  return search(0, arr.length - 1);
}
console.log( binarySearch(arr, 4) );

Python3 版本 while 循环

def binary_search(arr, left, right, key):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == key:
            return mid
        elif arr[mid] < key:
            left = mid + 1
        elif arr[mid] > key:
            right = mid - 1
    return -1

Python3 版本 递归

def binary_search(arr, start, end, key):
	if start > end:
		return -1
	mid = start + (end - start) // 2
	if arr[mid] > key:
		return binary_search(arr, start, mid - 1, key)
	if arr[mid] < key:
		return binary_search(arr, mid + 1, end, key)
	return mid

C# 版本

static int binary_search(int[] arr, int start, int end, int key)
{
    int mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        if (arr[mid] < key)
            start = mid + 1;
        else if (arr[mid] > key)
            end = mid - 1;
        else
            return mid; 
    }
    return -1;
}

Swift 版本

import Foundation
/// 二分搜索完全匹配
///
/// - Parameters:
///   - arr: 有序数组
///   - start: 起始位置
///   - end: 结束点
///   - key: 特点目标值
/// - Returns: 返回查找结果
func binarySearch(arr: [Int], start: Int, end: Int, key: Int) -> Int? {
    if start > end {
        return nil
    }
    let mid = start + (end - start) / 2
    if arr[mid] > key {
        return binarySearch(arr: arr, start: start, end: mid - 1, key: key)
    } else if arr[mid] < key {
        return binarySearch(arr: arr, start: mid + 1, end: end, key: key)
    } else {
        return mid
    }
}

golang 递归版本

func binary_search(arr []int, low, high, key int) int {
	if low > high {
		return -1
	}
	mid := low + (high-low)/2

	if arr[mid] > key {
		return binary_search(arr, low, mid-1, key)
	} else if arr[mid] < key {
		return binary_search(arr, mid+1, high, key)
	}

	return mid
}

golang 非递归版本

func binarySearch(arr []int, key int) int {
    low, high := 0, len(arr)-1
	for low <= high {
		mid := low + (high-low)/2
		if arr[mid] == key {
			return mid
		} else if key < arr[mid] {
			high = mid - 1
		} else if key > arr[mid] {
			low = mid + 1
		}
	}
	return -1
}

Java 递归

public static int binarySearch(int[] arr, int start, int end, int key){
    if (start > end)
        return -1;

    int mid = start + (end - start)/2;    //防止溢位
    if (arr[mid] > key)
        return binarySearch(arr, start, mid - 1, key);
    if (arr[mid] < key)
        return binarySearch(arr, mid + 1, end, key);
    return mid;  

}

Java while 循环

public static int binarySearch(int[] arr, int start, int end, int key){
    int result = -1;

    while (start <= end){
        int mid = start + (end - start)/2;    //防止溢位
        if (arr[mid] > key)
            end = mid - 1;
        else if (arr[mid] < key)
            start = mid + 1;
        else {
            result = mid ;  
            break;
        }
    }

    return result;

}

Julia版本

# Julia Sample : BinarySearch
function BinarySearch(A,Key)
	left,right = 1,length(A)

	while(left<=right)
		mid=left+floor(Int,((right-left)/2))
	
		if A[mid]==Key
			return mid
		elseif Key<A[mid]
			right = mid-1
		elseif Key>A[mid]
			left = mid+1
		end
	end
	return -1
end

# Main Code
A = [1,3,16,31,43,354,586]   # Already Arrange
println(A)                   # Original Array
println(BinarySearch(A,43))  # BinarySearch Search Array
println(BinarySearch(A,354)) # BinarySearch Search Array
println(BinarySearch(A,3))   # BinarySearch Search Array

历史

在1946年，约翰·莫奇利在摩尔学院讲座上第一次提出二分搜索的概念。1957年，威廉·皮特逊发表了第一个应用插值搜索的算法。在此时，每个发表的二分搜索算法只对长度为2的幂减一的数组有用。直到1960年，德里克·亨利·莱默发表了一个对于所有长度的数组都适用的算法。1962年，赫尔曼·博滕布鲁赫发表了一个用ALGOL 60写的二分搜索，将判断相等的步骤放到算法末尾。虽然将平均迭代次数增加一，但是每次迭代中的比较次数减少了1次。均匀二分搜索则是斯坦福大学的A. K.钱德拉在1971年发明的。1986年，伯纳德·查泽尔和列奥尼达斯·吉巴斯引入了分散层叠来解决计算几何中大量存在的搜索问题。

实现中的问题

尽管二分查找的基本思想相对简单，但细节可以令人难以招架 ... — 高德纳

当乔恩·本特利将二分搜索问题布置给专业编程课的学生时，百分之90的学生在花费数小时后还是无法给出正确的解答，主要因为这些错误程序在面对边界值的时候无法运行，或返回错误结果。1988年开展的一项研究显示，20本教科书里只有5本正确实现了二分搜索。不仅如此，本特利自己1986年出版的《编程珠玑》一书中的二分搜索算法存在整数溢出的问题，二十多年来无人发现。Java语言的库所实现的二分搜索算法中同样的溢出问题存在了九年多才被修复。

外部链接

• NIST Dictionary of Algorithms and Data Structures: binary search（页面存档备份，存于互联网档案馆）
• Google Research: Nearly All Binary Searches and Mergesorts are Broken（页面存档备份，存于互联网档案馆）.
• Binary search implemented in 12 languages（页面存档备份，存于互联网档案馆）.
• 程序员编程艺术第二十五章：Jon Bentley：90%无法正确实现二分查找（页面存档备份，存于互联网档案馆）
• https://leetcode.com/explore/learn/card/binary-search（页面存档备份，存于互联网档案馆）