介绍

在本教程中，我们将学习二进制搜索算法并将其用Java实现。

常规线性或者顺序搜索算法可方便地用于少量数据。
当大小增加时，在最坏的情况下，我们需要进行2n次比较，其中数组或者列表的大小为n。

因此，我们需要更有效的算法来搜索元素。
在本教程中，我们将探讨二进制搜索是一种简单而有效的算法，以及它是如何工作的。

二元搜索的核心算法

对于二进制搜索，数组中的元素必须按排序顺序。
让我们考虑一个升序的数组。
二进制搜索将要搜索的元素(即关键字)与数据集中中间的元素进行比较。
它基于以下三个(3)基本条件：

• 如果键小于中间元素，那么我们现在只需要在数组的前半部分搜索，
• 如果键大于中间元素，那么我们只需要在数组的后半部分搜索，
• 如果键等于数组中的中间元素，则搜索结束，
• 最后，如果未在整个数组中找到键，则应返回none或者-1。
  这表明不存在要搜索的元素。

二进制搜索示例

考虑一个由10个整数组成的排序数组，如下所示，

给定数组

假设我们正在搜索元素48。
在这种情况下，我们的键是48。

现在，我们将比较中间元素(即25)与我们需要搜索的元素(48)。
从" 48> 25"开始，我们消除了前半部分，因此必须在后半部分中搜索密钥。

为此，我们将低设置为Mid + 1，将高设置为数组的大小– 1或者最后一个元素的索引。

在下一次迭代中，我们将中间元素55与键进行比较。
从" 48 <55"开始，我们将不得不在数组的左半部分再次搜索元素。
相应地，low和high的值更新为5(不变)和Mid – 1。

接下来，现在中间元素是28，因此我们具有48> 28。
因此，我们需要进一步考虑数组的正确部分。

现在，低=中+ 1 = 6，高= 6(无变化)。

对于下一次迭代，中间元素等于要搜索的元素，即48。

因此，我们在索引6(中)找到了该数字。

用Java实现二进制搜索

现在让我们在Java中实现上述二进制搜索算法。

public class BinarySearch
{  
  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;  
      }  
      if ( low > high )
      {   
          return -1;
      }  
      return -1;
 }  
 public static void main(String args[])
 {  
      int arr[] = {10,18,19,20,25,28,48,55,62,70};  
      int key = 48;  
      int n=arr.length-1;  
      int index = binarySearch(arr,0,n,key);  
      System.out.println("The sorted array is: ");
      for(int i=0;i<n;i++)
      {
          System.out.print(arr[i] + " ");
      }
      System.out.println("\nElement to be searched: "+key);
      if (index == -1)  
          System.out.println("Unfortunately the Element is not found!");  
      else  
          System.out.println("The Element is found at the index: "+index);  
 }  
}  

二进制搜索算法的复杂性

二进制搜索算法的平均比较数为log2N。
因此，二进制搜索的时间复杂度为log2n。

就空间复杂度而言，对于二进制搜索，它是O(log n)。
另外，存储阵列需要O(n)空间。

其中n是给定排序数组的大小。