Java 二分查找

2025年7月14日 | 阅读 7 分钟

二分查找是一种高效的算法，用于在已排序的数组或列表中搜索目标元素。它遵循分治法的思想。它比线性搜索更快。请注意，在执行二分查找之前，数组或列表必须已排序。如果我们有一个未排序的数组或列表，我们可以使用 Arrays.sort(arr) 方法对数组进行排序。

二分查找的工作原理

已排序数据要求：首先，检查给定的数组或列表是否按升序排序。如果未排序，则必须先进行排序。
查找中间元素：查找数组或列表的中间元素以比较目标值。
比较和缩小范围
- 如果目标值与中间元素匹配，则找到其位置，搜索终止。
- 如果目标值小于中间元素，则搜索在左侧子数组中继续。
- 如果目标值大于中间元素，则搜索在右侧子数组中继续。
重复：在新的、缩小的搜索空间上重复步骤 2 和 3，直到找到目标值或搜索空间变为空（表示目标不存在）。

二分查找算法

BinarySearch(array, target):
    start = 0
    end = length(array) - 1
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid  // Target found at index mid
        else if array[mid] < target:
            start = mid + 1  // Search right half
        else:
            end = mid - 1    // Search left half
    return -1  // Target not found

二分查找示例

考虑以下数组。我们取了一个已排序的数组，我们要从中搜索值 28（目标元素）。

目标元素大于当前中间元素（即 28）。搜索移至右侧子数组。在右侧子数组中，中间元素是 32，目标元素（28）小于中间元素。因此，搜索移至数组的右侧。我们找到了目标元素。停止搜索。

二分查找的方法

执行二分查找有以下三种方法：

迭代方法
递归方法
使用 Arrays.binarySearch() 方法

二分查找示例

让我们在 Java 程序中实现二分查找逻辑。

示例

public class Main {
	public static void binarySearch(int arr[], int first, int last, int key) {
		int mid = (first + last) / 2;
		while (first <= last) {
			if (arr[mid] < key) {
				first = mid + 1;
			} else if (arr[mid] == key) {
				System.out.println("Element found at index: " + mid);
				break;
			} else {
				last = mid - 1;
			}
			mid = (first + last) / 2;
		}
		if (first > last) {
			System.out.println("Element is not found!");
		}
	}
	public static void main(String args[]) {
		int arr[] = { 10, 20, 30, 40, 50 };
		int key = 40;
		int last = arr.length - 1;
		binarySearch(arr, 0, last, key);
	}
}

编译并运行

输出

Element found at index: 3

使用迭代方法进行二分查找

Java 中的二分查找迭代方法是一种直接而有效的技术，用于在已排序的数组中查找目标元素的位置。此方法使用 while 循环，在每次迭代后将搜索范围减半，并根据与目标值的比较来调整起始和结束索引。

示例

public class Main {
	// Method to perform binary search on a sorted array
	public static int binarySearch(int[] arr, int target) {
		int left = 0;
		int right = arr.length - 1;
		while (left <= right) {
			int mid = left + (right - left) / 2;
			// Check if the target is present at mid
			if (arr[mid] == target) {
				return mid; // Target found
			}
			// If target greater than mid, ignore left half
			if (arr[mid] < target) {
				left = mid + 1;
			}
			// If the target is smaller than mid, ignore the right half
			else {
				right = mid - 1;
			}
		}
		// Target not found
		return -1;
	}
	// Main method to test the binarySearch method
	public static void main(String[] args) {
		int[] arr = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
		int target = 16;
		int result = binarySearch(arr, target);
		if (result == -1) {
			System.out.println("Element is not present in the array.");
		} else {
			System.out.println("Element found at index: " + result);
		}
	}
}

编译并运行

输出

Element found at index: 4

使用递归进行二分查找

递归方法在每次调用时将数组分成两半，根据与中间值比较的结果，将搜索区域缩小到左侧或右侧片段。递归继续进行，直到找到目标或搜索空间为空，此时算法终止。

让我们在 Java 程序中实现递归方法。

示例

public class Main {  
    public static int binarySearch(int arr[], int first, int last, int key){  
        if (last>=first){  
            int mid = first + (last - first)/2;  
            if (arr[mid] == key){  
            return mid;  
            }  
            if (arr[mid] > key){  
            return binarySearch(arr, first, mid-1, key);//search in left subarray  
            }else{  
            return binarySearch(arr, mid+1, last, key);//search in right subarray  
            }  
        }  
        return -1;  
    }  
    public static void main(String args[]){  
        int arr[] = {10,20,30,40,50};  
        int key = 30;  
        int last=arr.length-1;  
        int result = binarySearch(arr,0,last,key);  
        if (result == -1)  
            System.out.println("Element is not found!");  
        else  
            System.out.println("Element is found at index: "+result);  
    }  
}  

编译并运行

输出

Element is found at index: 2

使用 Arrays.binarySearch() 方法进行二分查找

Java Arrays 类为 byte、char、int、float、double、long、object 和 short 数据类型提供了不同的 binarySearch() 方法变体。它是一个静态方法。

该方法使用二分查找算法搜索指定值。在此调用之前，数组必须已排序（通过 sort(int[]) 方法）。如果未排序，结果是不确定的。如果数组包含多个具有指定值的元素，则不保证找到哪个元素。

语法

该方法接受两个参数：要搜索的数组和要搜索的元素（键）。当找到目标元素时，它返回元素的索引值；否则，它返回一个负值，表示插入点以保持数组排序。

示例

import java.util.Arrays;
public class Main {
	public static void main(String args[]) {
		int arr[] = { 10, 20, 30, 40, 50 };
		int key = 50;
		int result = Arrays.binarySearch(arr, key);
		if (result < 0)
			System.out.println("Element is not found!");
		else
			System.out.println("Element found at index: " + result);
	}
}

编译并运行

输出

Element found at index: 4

使用 Collections.binarySearch() 方法进行二分查找

Java Collections 类还提供了内置的 binarySearch() 方法。该方法使用二分查找算法搜索指定的对象。列表必须按升序排序。如果列表未排序，结果是不确定的。如果列表包含多个与指定对象相等的元素，则不保证找到哪个元素。它通过提供标准化的优化方法来查找元素，从而简化了 Java Collections 中的搜索操作。

语法

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key)

该方法接受两个参数：要搜索的列表和要搜索的键元素。它返回键元素的索引值。

示例

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<>();
		list.add(10);
		list.add(20);
		list.add(30);
		list.add(40);
		list.add(50);
		list.add(60);
		list.add(70);
		Collections.sort(list);
		int target = 60;
		int index = Collections.binarySearch(list, target);
		if (index >= 0) {
			System.out.println("Element found at index: " + index);
		} else {
			System.out.println("Element not found. Insertion point: " + (-index - 1));
		}
	}
}

编译并运行

输出

Element found at index: 5

复杂度分析

时间复杂度

在二分查找中，在每一步，算法都会将数组除以 2。经过 k 步后，大小变为 n / 2^k。当我们解 n / 2^k = 1 时，我们得到 k = log₂(n)。

情况	复杂度	描述
最佳	O(1)	在第一次比较时，元素位于中间索引处。
平均数	O(log n)	搜索空间在每一步都会减半，导致对数级别的比较。
最坏	O(log n)	元素位于末端之一或不存在，需要完整的 log(n) 步。

空间复杂度

方法	复杂度	描述
迭代	O(1)	为指针（low、high、mid）使用恒定空间。
递归	O(log n)	每次递归调用都会向调用堆栈添加一个新帧。