二に分ふん搜さがせ尋ひろ演算えんざん法ほう

在ざい计算机つくえ科学かがく中なか，二分にぶん查找算法さんぽう（英語えいご：binary search algorithm），也称折半せっぱん搜索そうさく算法さんぽう（英語えいご：half-interval search algorithm）、对数搜索そうさく算法さんぽう（英語えいご：logarithmic search algorithm），是ぜ一いち种在有ゆう序じょ数すう组中ちゅう查找某ぼう一いち特定とくてい元素げんそ的てき搜索そうさく算法さんぽう。搜索そうさく过程从数组的中ちゅう间元素げんそ开始，如果中ちゅう间元素げんそ正ただし好こう是ぜ要よう查找的てき元素げんそ，则搜索そうさく过程结束；如果某ぼう一特定元素大于或者小于中间元素，则在数すう组大于或小しょう于中间元素的すてき那な一半いっぱん中ちゅう查找，而且跟开始一样从中间元素开始比较。如果在ざい某ぼう一步骤数组为空，则代表だいひょう找不到いた。这种搜索そうさく算法さんぽう每ごと一次比较都使搜索范围缩小一半。

二に分ふん搜さがせ尋ひろ演算えんざん法ほう
概がい况
類別るいべつ	搜索そうさく算法さんぽう
資料しりょう結構けっこう	数かず组
复杂度ど
平均へいきん時間じかん複雜ふくざつ度ど	$O(\log n)$
最さい坏时间复杂度	$O(\log n)$
最さい优时间复杂度	$O(1)$
空間くうかん複雜ふくざつ度ど	迭代：$O(1)$ 递归：$O(\log n)$ （无尾お调用消しょう除じょ）
最さい佳けい解かい	Yes
相あい关变量的りょうてき定てい义

二分查找算法在情况下的复杂度是对数时间，进行$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 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;

}

历史

在ざい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