使用Java实现二分查找算法，在有序数组中查找特定元素

Question

假设您有一个有序的整数数组，并且需要查找数组中特定元素的索引。您决定使用二分搜索算法，这是有序数组的常用搜索算法。

编写一个Java程序，实现二分查找算法来搜索数组中的特定元素。您的程序应采用以下输入：有序整数数组以及要在数组中搜索的元素。您的程序应返回数组中元素的索引，如果未找到该元素，则返回 -1。

请务必解释二分搜索算法背后的逻辑以及它在您的实现中如何工作。

我尝试过的代码：

public class BinarySearch {
    public static int binarySearch(int[] arr, int x) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == x) {
                return mid;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // element not found
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int x = 5;
        int result = binarySearch(arr, x);
        
        if (result == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index " + result);
        }
    }
}

Answer 1

可以在

binarySearch()

中查看

java.util.Arrays

的实现：

private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

Answer 2

你可以看看这个二分查找代码在java中的实现。

import java.util.*;
public class binarysearch {
    
    public static int bs(int a[],int key){
        int start = 0 , end=a.length-1;
        while(start<=end){
            int mid = (start+end)/2;

            if(key==a[mid]){
                return mid;
            }

            if(key<a[mid]){
                end = mid-1;
            }
              else {
                start = mid+1;
              }
        } 
          return -1;
    }

    public static void main(String args[]){
      Scanner s = new Scanner(System.in);
      System.out.println("Enter the size of array");
        int size=s.nextInt();
        int n[]=new int[size];

        System.out.println("Enter elements of array");
        for(int i=0;i<size;i++){
          n[i]=s.nextInt();
        }
          System.out.println("Enter the number you want to find");
      
          int key = s.nextInt();
          
          System.out.println("Number found at index" + " " + bs(n, key));
        
          s.close();
    }
}

Answer 3

Java 中的二分查找

import java.util.Arrays;
class HelloWorld {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        Arrays.sort(arr);
        int index = Arrays.binarySearch(arr, 5);
        System.out.println("Element found at ->  "+index);
    }
}

输出： 元素位于 -> 2