使用 Java 的 DSA - 二分搜索

概述

二分搜索是一种非常快速的搜索算法。此搜索算法基于分而治之的原则。为了使此算法正常工作，数据集合应为排序形式。

二分搜索通过比较集合中最中间的项来搜索特定项。如果匹配，则返回项的索引。如果中间项大于项，则在中间项右侧的子数组中搜索项，否则在中间项左侧的子数组中搜索项。此过程在子数组上继续进行，直到子数组的大小减小到零。

二分查找将可搜索项减半，从而将需要进行的比较次数减少到非常少。

算法

二分查找(A:项数组，n:项总数，x:要搜索的项)
步骤 1:设置 lowerBound = 1
步骤 2:设置 upperBound = n
步骤 3:如果 upperBound < lowerBound 转到步骤 12
步骤 4:设置 midPoint = ( lowerBound + upperBound ) / 2
步骤 5:如果 A[midPoint] < x
步骤 6:设置 lowerBound = midPoint + 1
步骤 7:如果 A[midPoint] > x
步骤 8:设置 upperBound = midPoint - 1
步骤 9:如果 A[midPoint] = x 则转到步骤 11
步骤 10:转到步骤 3
步骤 11:打印在索引 midPoint 处找到的元素 x 并转到步骤 13
步骤 12:打印未找到的元素
步骤 13:退出

演示程序

package com.tutorialspoint.simplesearch;

import java.util.Arrays;

public class BinarySearchDemo {
    
   public static void main(String args[]){
      int[] sourceArray = {1,2,3,4,6,7,9,11,12,14,15,
      16,17,19,33,34,43,45,55,66,76,88};
      System.out.println("Input Array: " +Arrays.toString(sourceArray));
      printline(50);
      // 找到 55 的位置 
      int location = find(sourceArray, 55);
      if(location != -1){
         System.out.println("Element found at location: " +(location+1));
      }else {
         System.out.println("Element not found.");
      }    
   }

   public static int find(int[] intArray, int data){
      int lowerBound = 0;
      int upperBound = intArray.length -1;
      int midPoint = -1;
      int comparisons = 0;      
      int index = -1;
      while(lowerBound <= upperBound){
         System.out.println("Comparison " + (comparisons +1) ) ;
         System.out.println("lowerBound : "+lowerBound  
                           + " , intArray[" + lowerBound+"] = " 
                           + intArray[lowerBound]) ;
         System.out.println("upperBound : "+upperBound  
                           + " , intArray[" + upperBound+"] = " 
                           + intArray[upperBound]) ;
         comparisons++;
         // 计算中点
         midPoint = (lowerBound + upperBound) / 2;
         // 找到数据
         if(intArray[midPoint] == data){
		    index = midPoint;
            break;
         }
         else {
            // 如果数据较大 
            if(intArray[midPoint] < data){
               // 数据位于上半部分
               lowerBound = midPoint + 1;
            }
            // 数据较小 
            else{           
               // 数据在下半部分 
               upperBound = midPoint -1;
            }
         }               
      }
      System.out.println("Total comparisons made: " + comparisons);
      return index;
   }
   
   public static void printline(int count){
      for(int i=0;i <count-1;i++){
         System.out.print("=");
      }
      System.out.println("=");
   }
}

如果我们编译并运行上述程序，则会产生以下结果:

Input Array: [1, 2, 3, 4, 6, 7, 9, 11, 12, 14, 15, 16, 17, 19, 33, 34, 43, 45, 55, 66, 76, 88]
==================================================
Comparison 1
lowerBound : 0 , intArray[0] = 1
upperBound : 21 , intArray[21] = 88
Comparison 2
lowerBound : 11 , intArray[11] = 16
upperBound : 21 , intArray[21] = 88
Comparison 3
lowerBound : 17 , intArray[17] = 45
upperBound : 21 , intArray[21] = 88
Comparison 4
lowerBound : 17 , intArray[17] = 45
upperBound : 18 , intArray[18] = 55
Comparison 5
lowerBound : 18 , intArray[18] = 55
upperBound : 18 , intArray[18] = 55
Total comparisons made: 5
Element found at location: 19