设计与分析 - 二分搜索

二分搜索是一种快速搜索算法，运行时复杂度为 Ο(log n)。该搜索算法遵循分而治之的原则，因为它在搜索之前将数组分成两半。为了使该算法正常工作，数据收集应该是排序的形式。

二分搜索通过比较集合中最中间的项来查找特定的键值。如果发生匹配，则返回项目的索引。但如果中间项的值大于键值，则搜索中间项的右子数组。否则，搜索左侧子数组。此过程递归地继续，直到子数组的大小减小到零。

二进制搜索算法

二分查找算法

二分搜索算法是一种区间搜索方法，仅按区间进行搜索。二分搜索算法获取的输入必须始终位于排序数组中，因为它根据较大值或较小值将数组划分为子数组。该算法遵循以下过程 -

步骤 1 - 选择数组中的中间项并将其与要搜索的键值进行比较。如果匹配，则返回中位数的位置。

步骤 2 - 如果与键值不匹配，请检查键值是否大于或小于中值。

步骤 3 - 如果键更大，则在右侧子数组中执行搜索；但如果键值低于中值，则在左子数组中执行搜索。

步骤 4 - 迭代重复步骤 1、2 和 3，直到子数组的大小变为 1。

步骤 5 - 如果数组中不存在键值，则算法返回不成功的搜索。

伪代码

二分搜索算法的伪代码应该如下所示 -

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n

   while x not found
      if upperBound < lowerBound
         EXIT: x does not exists.

      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

      if A[midPoint] < x
         set lowerBound = midPoint + 1

      if A[midPoint] > x
         set upperBound = midPoint - 1

      if A[midPoint] = x
         EXIT: x found at location midPoint
   end while
end procedure

分析

由于二分搜索算法是迭代搜索，因此计算时间复杂度不像线性搜索算法那么容易。

每次不成功的迭代后，通过将输入数组划分为多个子数组来迭代搜索输入数组。因此，所形成的递推关系将是一个除函数。

用更简单的术语解释一下，

  • 在第一次迭代期间，在整个数组中搜索该元素。因此，数组的长度=n。

  • 在第二次迭代中，仅搜索原始数组的一半。因此，数组的长度 = n/2。

  • 在第三次迭代中，搜索前一个子数组的一半。这里，数组的长度= n/4。

  • 同样，在第 i次迭代时，数组的长度将变为 n/2 i

为了实现成功的搜索，在最后一次迭代之后，数组的长度必须为 1。因此，

n/2i = 1

这给了我们 -

n = 2i

两面都贴上原木，

log n = log 2i
log n = i. log 2
i = log n

二分查找算法的时间复杂度为O(log n)

例子

为了使二分搜索起作用，必须对目标数组进行排序。我们将通过一个图例来学习二分查找的过程。以下是我们的排序数组，假设我们需要使用二分搜索来搜索值 31 的位置。

带有图片示例的二进制搜索

首先，我们将使用以下公式确定数组的一半 -

mid = low + (high - low) / 2

此处为 0 + (9 - 0) / 2 = 4（整数值 4.5）。所以，4 是数组的中间。

第四个索引数组

现在我们将位置 4 存储的值与正在搜索的值（即 31）进行比较。我们发现位置 4 处的值是 27，这不匹配。由于该值大于 27 并且我们有一个已排序的数组，因此我们也知道目标值必须位于数组的上部。

location_4_value_27

我们将低值更改为中值 + 1，并再次找到新的中值。

low = mid + 1
mid = low + (high - low) / 2

我们的新中位数现在是 7。我们将位置 7 存储的值与目标值 31 进行比较。

at_loaction_7

存储在位置 7 的值不匹配，而是小于我们要查找的值。因此，该值必须位于该位置的下部。

location_7_not_ 匹配

因此，我们再次计算中值。这次是5。

at_location_5

我们将位置 5 存储的值与目标值进行比较。我们发现这是一个匹配。

location_5_matched

我们得出结论，目标值 31 存储在位置 5。

二分搜索将可搜索的项目减半，从而将比较的次数减少到非常少的数量。

例子

二分搜索是一种快速搜索算法，运行时复杂度为 Ο(log n)。该搜索算法的工作原理是分而治之。为了使该算法正常工作，数据收集应该采用排序的形式。

C C++ Java Python 
#include<stdio.h>
void binary_search(int a[], int low, int high, int key){
   int mid;
   mid = (low + high) / 2;
   if (low <= high) {
      if (a[mid] == key)
         printf("Element found at index: %d\n", mid);
      else if(key < a[mid])
         binary_search(a, low, mid-1, key);
      else if (a[mid] < key)
         binary_search(a, mid+1, high, key);
   } else if (low > high)
      printf("Unsuccessful Search\n");
}
int main(){
   int i, n, low, high, key;
   n = 5;
   low = 0;
   high = n-1;
   int a[10] = {12, 14, 18, 22, 39};
   key = 22;
   binary_search(a, low, high, key);
   key = 23;
   binary_search(a, low, high, key);
   return 0;
}

输出

Element found at index: 3
Unsuccessful Search

#include <iostream>
using namespace std;
void binary_search(int a[], int low, int high, int key){
   int mid;
   mid = (low + high) / 2;
   if (low <= high) {
      if (a[mid] == key)
         cout << "Element found at index: " << mid << endl;
      else if(key < a[mid])
         binary_search(a, low, mid-1, key);
      else if (a[mid] < key)
         binary_search(a, mid+1, high, key);
   } else if (low > high)
      cout << "Unsuccessful Search" <<endl;
}
int main(){
   int i, n, low, high, key;
   n = 5;
   low = 0;
   high = n-1;
   int a[10] = {12, 14, 18, 22, 39};
   key = 22;
   binary_search(a, low, high, key);
   key = 23;
   binary_search(a, low, high, key);
   return 0;
}

输出

Element found at index: 3
Unsuccessful Search

import java.io.*;
import java.util.*;
public class BinarySearch {
   static void binary_search(int a[], int low, int high, int key) {
      int mid = (low + high) / 2;
      if (low <= high) {
         if (a[mid] == key)
            System.out.println("Element found at index: " + mid);
         else if(key < a[mid])
            binary_search(a, low, mid-1, key);
         else if (a[mid] < key)
            binary_search(a, mid+1, high, key);
      } else if (low > high)
         System.out.println("Unsuccessful Search");
   }
   public static void main(String args[]) {
      int n, key, low, high;
      n = 5;
      low = 0;
      high = n-1;
      int a[] = {12, 14, 18, 22, 39};
      key = 22;
      binary_search(a, low, high, key);
      key = 23;
      binary_search(a, low, high, key);
   }
}

输出

Element found at index: 3
Unsuccessful Search

def binary_search(a, low, high, key):
   mid = (low + high) // 2
   if (low <= high):
      if(a[mid] == key):
         print("The element is present at index:", mid)
      elif(key < a[mid]):
         binary_search(a, low, mid-1, key)
      elif (a[mid] < key):
         binary_search(a, mid+1, high, key)
   if(low > high):
      print("Unsuccessful Search")

a = [6, 12, 14, 18, 22, 39, 55, 182]
n = len(a)
low = 0
high = n-1
key = 22
binary_search(a, low, high, key)
key = 54
binary_search(a, low, high, key)

输出

The element is present at index: 4
Unsuccessful Search