二分查找算法

2025年8月14日 | 阅读10分钟

在列表中搜索一个项目有时可能是一个相当大的挑战，你同意吗？这就是搜索功能派上用场的地方。当你找到你要找的东西时，就被认为是搜索。然而，如果你一无所获，那就算作一次尝试。

搜索项目有多种方法，其中线性搜索和二分查找是两种选择。今天，让我们来探讨一下二分查找技术。

顾名思义，二分查找是针对列表的。因此，在使用此方法之前，请确保您的列表已正确排序。

这种二分查找方法遵循“分而治之”的策略。它将列表分成两部分，并将目标项与元素进行比较。如果匹配，恭喜您！您已命中目标。如果不是，则根据比较结果，搜索将继续到右侧。

请记住，二分查找在列表上有效。如果您的列表未排序，则在使用此方法之前，必须先对其进行排序。

注意：二分查找可以应用于已排序的数组元素。如果列表元素未按排序顺序排列，我们必须先对其进行排序。

现在，让我们看一下二分查找的算法。

算法

Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to search
Step 1: set beg = lower_bound, end = upper_bound, pos = - 1
Step 2: repeat steps 3 and 4 while beg <=end
Step 3: set mid = (beg + end)/2
Step 4: if a[mid] = val
set pos = mid
print pos
go to step 6
else if a[mid] > val
set end = mid - 1
else
set beg = mid + 1
[end of if]
[end of loop]
Step 5: if pos = -1
print "value is not present in the array"
[end of if]
Step 6: exit

现在，让我们看一下二分查找算法的工作原理。

那么，让我们深入了解一下这种二分查找技术是如何运作的。它可能不像看起来那么复杂。

设想这样一个场景；您正在处理一个名为“a”的数组。您的目标是在其中查找一个值“val”。数组包含一个起始元素（下界）和一个结束元素（上界）。

首先，将“beg”赋值为下界，“end”赋值为上界，并将“pos”赋值为 1（暂时只是一个标记）。

然后，您进入一个循环，直到“beg”大于“end”，您将不断重复以下步骤：

通过取“beg”和“end”的平均值来计算中间索引“mid”。
检查“mid”处的值是否等于“val”。如果是，您就挖到金矿了！将“pos”设置为“mid”并打印其位置。然后，您可以退出循环。
如果“mid”处的值大于“val”，则表示“val”可能在数组的左半部分。因此，您将“end”更新为“mid-1”。
如果“mid”处的值小于“val”，则表示“val”可能在右半部分。将“beg”更新为“mid + 1”。

循环结束后，如果“pos”仍然是 -1，则您要查找的值不在数组中。否则，您已找到其位置。

二分查找的工作原理

现在，让我们看一下二分查找算法的工作原理。

为了理解二分查找算法的工作原理，让我们取一个已排序的数组。通过示例理解二分查找的工作原理会更容易。

有两种方法可以实现二分查找算法：

迭代法
递归法

二分查找的递归方法遵循分而治之的方法。

设数组的元素为：

设要搜索的元素为 K = 56

我们必须使用以下公式来计算数组的中值——

所以，在给定的数组中——

beg = 0

end = 8

mid = (0 + 8)/2 = 4。所以，4是数组的中值。

现在，找到了要搜索的元素。因此，算法将返回匹配元素的索引。

二分查找复杂度

现在，让我们看看二分查找在最佳情况、平均情况和最坏情况下的时间复杂度。我们还将查看二分查找的空间复杂度。

1. 时间复杂度

情况	时间复杂度
最佳情况	O(1)
平均情况	O(logn)
最坏情况	O(logn)

最佳情况复杂度——在二分查找中，当要搜索的元素在第一次比较中找到时，即当第一个中间元素本身就是要搜索的元素时，就出现了最佳情况。二分查找的最佳情况时间复杂度为O(1)。
平均情况复杂度——二分查找的平均情况时间复杂度为O(logn)。
最坏情况复杂度——在二分查找中，当我们需要不断缩小搜索范围直到只剩一个元素时，就会出现最坏情况。二分查找的最坏情况时间复杂度为O(logn)。

2. 空间复杂度

空间复杂度

O(1)

二分查找的空间复杂度为 O(1)。

二分查找的实现

现在，让我们看一下不同编程语言中的二分查找程序。

二分查找的优点

速度快；与搜索其他搜索方法相比，二分查找速度更快，尤其是在处理大型列表时。查找元素所需的时间是随着列表大小呈对数增长，而不是线性增长。
效率高。由于二分查找在每一步后都会消除剩余元素的一半，因此它非常高效，不会浪费时间检查不必要的元素。
易于实现。该算法易于理解，因此可以用各种编程语言轻松编写和实现。
在已排序的列表中效果很好。只要列表已排序，二分查找就可以快速可靠地找到目标元素。
空间效率高。与其他搜索算法不同，二分查找不需要额外的数据结构或内存分配。它直接在给定列表上运行，因此空间效率高。
用途广泛。二分查找不仅可以用于查找特定元素，还可以用于查找已排序列表中元素的第一次或最后一次出现，甚至用于查找目标值的最接近元素。
适应性强。二分查找的基本思想可以扩展和适应以解决各种其他问题，例如查找数字的平方根或在旋转排序数组中搜索。
可靠且可预测。使用二分查找，您可以确切地知道找到目标元素（或确定它不存在）需要多少步，这使其成为一个可靠且可预测的算法。

总而言之，二分查找算法是一种强大的工具，它结合了速度、效率、简单性和多功能性，使其成为各种领域和应用程序中搜索已排序列表的首选。

程序：编写一个用 C 语言实现二分查找的程序。

#include <stdio.h>
int binarySearch(int a[], int beg, int end, int val)  
{  
    int mid;  
    if(end >= beg)   
    {        mid = (beg + end)/2;  
/* if the item to be searched is present at middle */
        if(a[mid] == val)  
        {               
            return mid+1;  
        }  
            /* if the item to be searched is smaller than middle, then it can only be in left subarray */
        else if(a[mid] < val)   
        {
            return binarySearch(a, mid+1, end, val);  
        }  
            /* if the item to be searched is greater than middle, then it can only be in right subarray */
        else   
        {
            return binarySearch(a, beg, mid-1, val);  
        }        
    }  
    return -1;   
} 
int main() {
  int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
  int val = 40; // value to be searched
  int n = sizeof(a) / sizeof(a[0]); // size of array
  int res = binarySearch(a, 0, n-1, val); // Store result
  printf("The elements of the array are - ");
  for (int i = 0; i < n; i++)
  printf("%d ", a[i]); 
  printf("\nElement to be searched is - %d", val);
  if (res == -1)
  printf("\nElement is not present in the array");
  else
  printf("\nElement is present at %d position of array", res);
  return 0;
}

输出

程序：编写一个用 Python 实现二分查找的程序。

defbinary_search(sorted_list, target):
start = 0
end = len(sorted_list) - 1

while start <= end:
mid = (start + end) // 2
ifsorted_list[mid] == target:
return mid
elifsorted_list[mid] > target:
end = mid - 1
else:
start = mid + 1

return -1
my_list = [2, 5, 7, 9, 12, 15, 18]
target_value = 9
index = binary_search(my_list, target_value)

if index == -1:
print("Value not found in the list")
else:
print(f"Value found at index {index}")

输出

程序：编写一个用 C++ 实现二分查找的程序。

#include <iostream>
using namespace std;
int binarySearch(int a[], int beg, int end, int val)  
{  
    int mid;  
    if(end >= beg)   
    {
        mid = (beg + end)/2;  
/* if the item to be searched is present at middle */
        if(a[mid] == val)  
        {               
            return mid+1;  
        }  
            /* if the item to be searched is smaller than middle, then it can only be in left subarray */
        else if(a[mid] < val)   
        {
            return binarySearch(a, mid+1, end, val);  
        }  
        /* if the item to be searched is greater than middle, then it can only be in right subarray */    
    else   
        {
            return binarySearch(a, beg, mid-1, val);  
        }       
    }  
    return -1;   
} 
int main() {
  int a[] = {10, 12, 24, 29, 39, 40, 51, 56, 70}; // given array
  int val = 51; // value to be searched
  int n = sizeof(a) / sizeof(a[0]); // size of array
  int res = binarySearch(a, 0, n-1, val); // Store result
  cout<<"The elements of the array are - ";
  for (int i = 0; i < n; i++)
  cout<<a[i]<<" ";  
  cout<<"\nElement to be searched is - "<<val; 
  if (res == -1)
  cout<<"\nElement is not present in the array";
  else
  cout<<"\nElement is present at "<<res<<" position of array";
  return 0;
}

输出

程序：编写一个用 C# 实现二分查找的程序。

using System;
class BinarySearch {
    static int binarySearch(int[] a, int beg, int end, int val)  
    {  
        int mid;  
        if(end >= beg)   
        {
            mid = (beg + end)/2;  
            if(a[mid] == val)  
            {  
                return mid+1;  /* if the item to be searched is present at middle */
            }  
            /* if the item to be searched is smaller than middle, then it can only be in left subarray */
            else if(a[mid] < val)   
            {
                return binarySearch(a, mid+1, end, val);  
            }  
            /* if the item to be searched is greater than middle, then it can only be in right subarray */
            else  
            {
                return binarySearch(a, beg, mid-1, val);  
            }  
        }  
        return -1;  
    } 
    static void Main() {
        int[] a = {9, 11, 23, 28, 38, 45, 50, 56, 70}; // given array
        int val = 70; // value to be searched
        int n = a.Length; // size of array
        int res = binarySearch(a, 0, n-1, val); // Store result
        Console.Write("The elements of the array are - ");
        for (int i = 0; i < n; i++)
        {
            Console.Write(a[i] + " ");
        }
        Console.WriteLine();
        Console.WriteLine("Element to be searched is - " + val);
        if (res == -1)
        Console.WriteLine("Element is not present in the array");
        else
        Console.WriteLine("Element is present at " + res + " position of array");
    }
    }

输出

程序：编写一个用 Java 实现二分查找的程序。

class BinarySearch {
    static int binarySearch(int a[], int beg, int end, int val)  
    {  
        int mid;  
        if(end >= beg)   
        {
            mid = (beg + end)/2;  
            if(a[mid] == val)  
            {  
                return mid+1;  /* if the item to be searched is present at middle 
*/
            }  
            /* if the item to be searched is smaller than middle, then it can only 
be in left subarray */
            else if(a[mid] < val)   
            {
                return binarySearch(a, mid+1, end, val);  
            }  
            /* if the item to be searched is greater than middle, then it can only be 
in right subarray */
            else  
            {
                return binarySearch(a, beg, mid-1, val);  
            }  
        }  
        return -1;  
    } 
    public static void main(String args[]) {
        int a[] = {8, 10, 22, 27, 37, 44, 49, 55, 69}; // given array
        int val = 37; // value to be searched
        int n = a.length; // size of array
        int res = binarySearch(a, 0, n-1, val); // Store result
        System.out.print("The elements of the array are: ");
        for (int i = 0; i < n; i++)
        {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        System.out.println("Element to be searched is: " + val);
        if (res == -1)
        System.out.println("Element is not present in the array");
        else
        System.out.println("Element is present at " + res + " position of array");
    }
    }

输出

程序：编写一个用 PHP 实现二分查找的程序。

<?php
function binarySearch($a, $beg, $end, $val)  
{  
if($end >= $beg)   
{
	$mid = floor(($beg + $end)/2);  
	if($a[$mid] == $val)  
	{
		return $mid+1;  /* if the item to be searched is present at middle */
	}  
	/* if the item to be searched is smaller than middle, then it can only  be in left subarray */
	else if($a[$mid] < $val)   
	{
		return binarySearch($a, $mid+1, $end, $val);  
	}  
	/* if the item to be searched is greater than middle, then it can only be in right subarray */
	else  
	{
		return binarySearch($a, $beg, $mid-1, $val);  
	}  
}  
return -1;  
}
	$a = array(7, 9, 21, 26, 36, 43, 48, 54, 68); // given array
	$val = 68; // value to be searched
	$n = sizeof($a); // size of array
	$res = binarySearch($a, 0, $n-1, $val); // Store result 
	echo "The elements of the array are: ";
	for ($i = 0; $i < $n; $i++)
		echo " " , $a[$i];
	echo "<br>" , "Element to be searched is: " , $val;
	if ($res == -1)
		echo "<br>" , "Element is not present in the array";
	else
		echo "<br>" , "Element is present at " , $res , " position of array";
?>

输出