设计与分析 - 二分搜索

二分搜索法是一种遵循分而治之技术的搜索算法。这是基于有序搜索的思想，其中算法将排序列表分为两半并执行搜索。如果要查找的键值低于排序列表的中点值，则在左半部分查找；否则它会搜索右半部分。如果数组未排序，则使用线性搜索来确定位置。

二分查找算法

在此算法中，我们要查找元素 x 是否属于存储在数组Numbers [] 中的一组数字。其中l和r表示要执行搜索操作的子数组的左索引和右索引。

Algorithm: Binary-Search(numbers[], x, l, r)
   if l = r then
      return l
   else
      m := $\lfloor (l + r) / 2\rfloor$
   if x ≤ numbers[m] then
      return Binary-Search(numbers[], x, l, m)
   else
      return Binary-Search(numbers[], x, m+1, r)

例子

在此示例中，我们将搜索元素 63。

分析

线性搜索的运行时间为O(n)。而二分查找则在O(log n)时间内产生结果。

令T(n)为n 个元素的数组中最坏情况下的比较次数。

因此，

$$T\left ( n \right )=\left\{\begin{matrix} 0 & if\: n=1\\ T\left ( \frac{n}{2} \right )+1 & 否则 \ \ \end{矩阵}\right.$$

使用此递推关系T(n)=log n。

因此，二分查找使用O(log n)时间。

例子

在下面的实现中，我们尝试通过应用二元搜索算法从值列表中搜索整数值。

C C++ Java Python

#include<stdio.h>
int binarySearch(int arr[], int p, int r, int num){
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
         return mid ;
      if (arr[mid] > num)
         return binarySearch(arr, p, mid-1, num);
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}
int main(){
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   printf("Array elements are: \n");
   for(int i = 0; i<n; i++){
       printf("%d ", arr[i]);
   }
   printf("\n");
   int num = 15;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1) {
      printf("%d is not found in the array", num);
   } else {
      printf("%d is found at index %d in the array", num, index);
   }
   return 0;
 }

输出

Array elements are: 
1 3 7 15 18 20 25 33 36 40 
15 is found at index 3 in the array

#include<iostream>
using namespace std;
int binarySearch(int arr[], int p, int r, int num){
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
         return mid ;
      if (arr[mid] > num)
         return binarySearch(arr, p, mid-1, num);
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}
int main(){
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   cout<<"Array elements are: "<<endl;
   for(int i = 0; i<n; i++){
       cout<<arr[i]<<" ";
   }
   cout<<"\n";
   int num = 15;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1) {
      cout<< num <<" is not found in the array";
   } else {
      cout<< num <<" is found at index "<< index <<" in the array";
   }
   return 0;
 }

输出

Array elements are: 
1 3 7 15 18 20 25 33 36 40 
15 is found at index 3 in the array

public class Binary_Search {
   public static int binarySearch(int arr[], int low, int high, int key) {
      int mid = (low + high)/2;
      while( low <= high ) {
         if ( arr[mid] < key ) {
            low = mid + 1;
         } else if ( arr[mid] == key ) {
            return mid;
         } else {
            high = mid - 1;
         }
         mid = (low + high)/2;
      }
      return -1;
   }
   public static void main(String args[]) {
      int[] arr = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
      System.out.println("Array elements are: ");
      for(int i = 0; i<arr.length; i++){
          System.out.print(arr[i] + " ");
      }
      System.out.println("");
      int key = 15;
      int high=arr.length-1;
      int i = binarySearch(arr,0,high,key);
      if (i != -1) {
         System.out.println(key + " is found at index " + i + " in the array");
      } else {
         System.out.println(key + " is not found in the array1");
      }
   }
}

输出

Array elements are: 
1 3 7 15 18 20 25 33 36 40 
15 is found at index 3 in the array

def binarySearch(arr, low, high, key):
   mid = (low + high)//2
   while( low <= high ):
      if ( arr[mid] < key ):
         low = mid + 1
      elif ( arr[mid] == key ):
         return mid
      else:
         high = mid - 1
      mid = (low + high)//2
   return -1;

arr = [1, 3, 7, 15, 18, 20, 25, 33, 36, 40]
print("Array elements are: ")
print(arr)
key = 15
high=len(arr)-1
i = binarySearch(arr,0,high,key)
if (i != -1):
   print(key , "is found at index" , i , "in the array")
else:
   print("key is not found in the array")

输出

Array elements are: 
[1, 3, 7, 15, 18, 20, 25, 33, 36, 40]
15 is found at index 3 in the array