close

二分查找 (Binary Search) 算法 Java

二分查找算法是一种有效的 Java 编程方法，用于在已排序的数组中查找特定值。 这种方法不断地将数组分成两部分，并将搜索值与中间元素进行比较。

二分查找算法的工作原理

二分搜索算法首先将搜索值与数组的中间元素进行比较。 如果搜索值等于中间元素，算法将返回该元素的位置。 如果搜索值小于中间元素，算法将继续在数组的左半部分搜索。 如果搜索值更大，算法将继续在数组的右半部分搜索。 重复此过程，直到找到搜索值或没有更多元素可供搜索。

二分查找算法的优点和缺点

优点：

  • 高效率： 该算法每一步消除一半的元素，优化大数组的搜索。
  • 时间复杂度低： 该算法的时间复杂度为O(log n)，对于大型数据集非常有效。

缺点：

  • 排序数组要求： 该算法仅适用于排序数组。

示例与说明

考虑使用二分搜索算法在 中的排序整数数组中查找特定整数的示例 Java。 

public class BinarySearchExample {  
    public static int binarySearch(int[] array, int target) {  
        int left = 0;  
        int right = array.length- 1;  
  
        while(left <= right) {  
            int mid = left +(right- left) / 2;  
  
            if(array[mid] == target) {  
                return mid; // Return position if found  
            } else if(array[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid- 1;  
            }  
        }  
        return -1; // Return -1 if not found  
    }  
  
    public static void main(String[] args) {  
        int[] numbers = { 1, 3, 5, 7, 9, 11, 13, 15 };  
        int target = 9;  
  
        int position = binarySearch(numbers, target);  
  
        if(position != -1) {  
            System.out.println("Element " + target + " found at position " + position);  
        } else {  
            System.out.println("Element " + target + " not found in the array");  
        }  
    }  
}

在此示例中，我们使用二分搜索算法在已排序的整数数组中查找数字 9。 该算法迭代数组并将搜索值与中间值进行比较。 在本例中，数字 9 位于数组中的位置 4（从 0 开始的索引）处。

虽然此示例演示了二分搜索算法如何在排序的整数数组中查找元素，但它也可以应用于 Java 编程中的其他搜索场景。