打开主菜单

二分搜索算法

搜索算法
(重定向自折半搜索算法

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

二分搜索算法
Binary search into array.png
分类 搜索算法
数据结构 数组
最坏时间复杂度
最优时间复杂度
平均时间复杂度
最坏空间复杂度 迭代:
递归:
(无尾调用消除)

二分搜索在情况下的复杂度是对数时间,进行次比较操作(在此处是数组的元素数量,大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];
function binarySearch (arr, val) {
    var low = 0,
        high = arr.length - 1;
    while (low <= high) {
        var mid = parseInt( (low + high) / 2 );
        if (val == arr[mid]) {
            return mid;
        }else if (val > arr[mid]) {
            low = mid + 1;
        }else if (val < arr[mid]) {
            high = mid - 1;
        }
    }
    return -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;
}

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, low, high, hkey int) int {
	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;

}

参考编辑

  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. ^ 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, pp. 461–463.
  7. ^ Sedgewick & Wayne 2011,§3.1, subsection "Range queries".

外部链接编辑