二分查找算法

✍ dations ◷ 2025-07-04 17:38:18 #二分查找算法

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

二分查找算法在最坏情况（英语：Best, worst and average case）下是对数时间复杂度的，需要进行 ${displaystyle O(log n)}$ 匹配，也就是查找一个目标值的位置。不过，因为有序数组的顺序性，将二分搜索算法扩展到能适用大致匹配并不是很重要。举例来说，二分搜索算法可以用来计算一个赋值的排名（或称秩，比它更小的元素的数量）、前趋（下一个最小元素）、后继（下一个最大元素）以及最近邻。查找两个值之间的元素数目的范围查询（英语：Range query (data structures)）可以借由两个排名查询（又称秩查询）来执行。

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

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 > khey)		return binary_search(arr, start, mid - 1, khey);	else if (arr < 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 < key)			start = mid + 1;		else if (arr > key)			end = mid - 1;		else {            // 最後檢測相等是因為多數搜尋狀況不是大於要不就小於			ret = mid;              break;        }	}		return ret;     // 单一出口}

javascript 版本

var arr = ;const binarySearch = (arr, target) => {  const search = (start, end) => {    if (start > end) return -1;    const mid = start + Math.floor((end - start) / 2);    if (arr > target) {      return search(0, mid - 1);    } else if (arr < 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 == hkey:            return mid        elif arr < hkey:            left = mid + 1        elif arr > 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 > hkey:		return binary_search(arr, start, mid - 1, hkey)	if arr < hkey:		return binary_search(arr, mid + 1, end, hkey)	return mid

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

this is c++

Swift 版本

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

Julia (编程语言)

# Julia Sample : BinarySearchfunction BinarySearch(A,Key)	left,right = 1,length(A)	while(left<=right)		mid=left+floor(Int,((right-left)/2))			if A==Key			return mid		elseif Key<A			right = mid-1		elseif Key>A			left = mid+1		end	end	return -1end# Main CodeA =    # Already Arrangeprintln(A)                   # Original Arrayprintln(BinarySearch(A,43))  # BinarySearch Search Arrayprintln(BinarySearch(A,354)) # BinarySearch Search Arrayprintln(BinarySearch(A,3))   # BinarySearch Search Array

历史

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

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

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