Java 二分法检索算法代码实现详解

什么是二分法检索算法

二分法（Binary Search）又称折半查找法，它要求待查找的序列是有序的，每次查找都取中间位置的值进行比较，然后将查找的区域缩小为左边或右边的一半，直到找到目标值为止。

代码实现

下方是 Java 语言实现的二分法算法代码:

public static int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

上述代码中，需要传入两个参数：

• nums：表示一个有序的数组。
• target：表示需要查找的目标值。

代码中的实现方式是采用二分查找的方式找到目标值，找到时返回其对应的下标；如果没有找到，则返回-1表示没有找到。

示例说明

示例1

对于有序数组 nums=[1, 3, 5, 7, 9, 11]，如果需要查找的目标值是 7，则可以调用上述的二分法算法进行查找。调用代码如下：

int[] nums = {1, 3, 5, 7, 9, 11};
int target = 7;
int index = binarySearch(nums, target);
System.out.println("目标值在数组中的下标为：" + index);

程序输出结果为：

目标值在数组中的下标为：3

说明目标值 7 在数组中的下标为 3。

示例2

对于有序数组 nums=[1, 3, 5, 7, 9, 11]，如果需要查找的目标值是 4，则可以调用上述的二分法算法进行查找。调用代码如下：

int[] nums = {1, 3, 5, 7, 9, 11};
int target = 4;
int index = binarySearch(nums, target);
System.out.println("目标值在数组中的下标为：" + index);

程序输出结果为：

目标值在数组中的下标为：-1

说明目标值 4 在数组中未找到。