二分查找算法

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

二分查找算法
Binary search into array.png
概况
类别搜索算法
数据结构数组
复杂度
平均时间复杂度
最坏时间复杂度
最优时间复杂度
空间复杂度迭代:
递归:
(无尾调用消除)
最佳解Yes
相关变量的定义

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

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

算法

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

步骤

给予一个包含 个带值元素的数组 或是记录 ,使 ,以及目标值 ,还有下列用来查找  中位置的子程序[3]

  1.     
  2. 如果 ,则查找以失败告终。
  3.  (中间值元素)为 。(具体实现中,为防止算术溢出,一般采用 代替。)
  4. 如果 ,令  并回到步骤二。
  5. 如果 ,令  并回到步骤二。
  6.  ,查找结束;回传值 

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

大致匹配

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

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

复杂度分析

时间复杂度
折半搜索每次把搜索区域减少一半,时间复杂度为 。(n代表集合中元素的个数)
空间复杂度
 。虽以递归形式定义,但是尾递归,可改写为循环。

应用

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

示例代码

C 版本- 递归

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

	int mid = start + (end - start) / 2;    //直接平均可能會溢位,所以用此算法
	if (arr[mid] > khey)
		return binary_search(arr, start, mid - 1, khey);
	else if (arr[mid] < khey)
		return binary_search(arr, mid + 1, end, khey);
	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, hkey):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == hkey:
            return mid
        elif arr[mid] < hkey:
            left = mid + 1
        elif arr[mid] > hkey:
            right = mid - 1
    return -1

Python3 版本 递归

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


C# 版本

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

Swift 版本

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

golang 递归版本

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

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

	return mid
}

golang 非递归版本

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

Java 递归

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

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

}

Java while 循环

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

    while (start <= end){
        int mid = start + (end - start)/2;    //防止溢位
        if (arr[mid] > hkey)
            end = mid - 1;
        else if (arr[mid] < hkey)
            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年,约翰·莫奇利摩尔学院讲座英语Moore School Lectures上第一次提出二分搜索的概念。[8]1957年,威廉·皮特逊英语William Wesley Peterson发表了第一个应用插值搜索的算法[8][9]。在此时,每个发表的二分搜索算法只对长度为2的幂减一的数组有用。[10]直到1960年,德里克·亨利·莱默发表了一个对于所有长度的数组都适用的算法[11]。1962年,赫尔曼·博滕布鲁赫发表了一个用ALGOL 60写的二分搜索,将判断相等的步骤放到算法末尾。虽然将平均迭代次数增加一,但是每次迭代中的比较次数减少了1次。[12]均匀二分搜索则是史丹佛大学的A. K.钱德拉在1971年发明的[8]。1986年,伯纳德·查泽尔列奥尼达斯·吉巴斯引入了分散层叠来解决计算几何中大量存在的搜索问题[13][14][15]

实现中的问题

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

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

参考

  1. ^ Willams, Jr., Louis F. A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference: 95–101. 1975. doi:10.1145/503561.503582. 
  2. ^ 2.0 2.1 Knuth 1998,§6.2.1 ("Searching an ordered table"), subsection "Binary search".
  3. ^ Knuth 1998,§6.2.1 ("Searching an ordered table"), subsection "Algorithm B".
  4. ^ Bottenbruch, Hermann. Structure and Use of ALGOL 60. Journal of the ACM. 1962, 9 (2): 161–211.  Procedure is described at p. 214 (§43), titled "Program for Binary Search".
  5. ^ 5.0 5.1 Sedgewick & Wayne 2011,§3.1, subsection "Rank and selection".
  6. ^ Goldman & Goldman 2008,第461–463页.
  7. ^ Sedgewick & Wayne 2011,§3.1, subsection "Range queries".
  8. ^ 8.0 8.1 8.2 Knuth 1998,§6.2.1 ("Searching an ordered table"), subsection "History and bibliography".
  9. ^ Peterson, William Wesley. Addressing for random-access storage. IBM Journal of Research and Development. 1957, 1 (2): 130–146. doi:10.1147/rd.12.0130. 
  10. ^ "2n−1". OEIS A000225页面存档备份,存于互联网档案馆). Retrieved 7 May 2016.
  11. ^ Lehmer, Derrick. Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics 10. 1960: 180–181. doi:10.1090/psapm/010.  参数|journal=与模板{{cite conference}}不匹配(建议改用{{cite journal}}|book-title=) (帮助)
  12. ^ Bottenbruch, Hermann. Structure and use of ALGOL 60. Journal of the ACM. 1962-04-01, 9 (2): 161–221. ISSN 0004-5411. doi:10.1145/321119.321120.  Procedure is described at p. 214 (§43), titled "Program for Binary Search".
  13. ^ Chazelle, Bernard; Liu, Ding. Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. ACM: 322–329. 2001-07-06 [2018-06-30]. ISBN 978-1-58113-349-3. doi:10.1145/380752.380818. (原始内容存档于2018-10-29). 页面存档备份,存于互联网档案馆
  14. ^ Chazelle, Bernard; Guibas, Leonidas J. Fractional cascading: I. A data structuring technique (PDF). Algorithmica. 1986, 1 (1-4): 133–162 [2019-10-06]. CiteSeerX 10.1.1.117.8349 . doi:10.1007/BF01840440. (原始内容存档 (PDF)于2016-03-03). 页面存档备份,存于互联网档案馆
  15. ^ Chazelle, Bernard; Guibas, Leonidas J., Fractional cascading: II. Applications (PDF), Algorithmica, 1986, 1 (1-4): 163–191 [2019-10-06], doi:10.1007/BF01840441, (原始内容存档 (PDF)于2016-03-04) 
  16. ^ Bentley 2000,§4.1 ("The Challenge of Binary Search").
  17. ^ Pattis, Richard E. Textbook errors in binary searching. SIGCSE Bulletin. 1988, 20: 190–194. doi:10.1145/52965.53012. 
  18. ^ Bloch, Joshua. Extra, extra – read all about it: nearly all binary searches and mergesorts are broken. Google Research Blog. 2006-06-02 [2016-04-21]. (原始内容存档于2016-04-01). 页面存档备份,存于互联网档案馆
  • Sahni, Sartaj. Data Structures, Algorithms, and Applications in C++. McGraw2-Hill. 1998. ISBN 978-0072362268. 
  • Knuth, Donald. Fundamental algorithms. The Art of Computer Programming 1 3rd. Reading, MA: Addison-Wesley Professional. 1997. ISBN 978-0-201-89683-1. 
  • Knuth, Donald. Sorting and searching. The Art of Computer Programming 3 2nd. Reading, MA: Addison-Wesley Professional. 1998. ISBN 978-0-201-89685-5. 
  • Knuth, Donald. Combinatorial algorithms. The Art of Computer Programming 4A 1st. Reading, MA: Addison-Wesley Professional. 2011. ISBN 978-0-201-03804-0. 
  • Moffat, Alistair; Turpin, Andrew. Compression and coding algorithms. Hamburg, Germany: Kluwer Academic Publishers. 2002. ISBN 978-0-7923-7668-2. doi:10.1007/978-1-4615-0935-6. 
  • Sedgewick, Robert; Wayne, Kevin. Algorithms 4th. Upper Saddle River, New Jersey: Addison-Wesley Professional. 2011 [2019-05-15]. ISBN 978-0-321-57351-3. (原始内容存档于2014-07-15).  Condensed web version:  ; book version  .
  • Stroustrup, Bjarne. The C++ programming language 4th. Upper Saddle River, New Jersey: Addison-Wesley Professional. 2013. ISBN 978-0-321-56384-2. 

外部链接