算法系列之搜素算法-二分查找

news/2025/2/26 3:13:44

在算法中，查找算法是处理数据集合的基础操作之一。二分查找（Binary Search）是一种高效的查找算法，适用于有序数组或列表。本文将介绍二分查找的基本原理、Java实现。

二分查找介绍

二分查找是一种在有序数组中查找特定元素的算法。它的基本思想是通过将数组分成两半，逐步缩小查找范围，直到找到目标元素或确定目标元素不存在。

算法步骤

初始化：设定查找范围的起始点 left 和结束点 right，初始时 left = 0，right = 数组长度 - 1。
计算中间点：计算中间点 mid = left + (right-left) / 2。

注：因为 left和right都是int类型，为了避免left+right 超出int类型的最大值。此处使用 mid = left + (right-left) / 2 来计算中间索引。

比较中间元素：

如果中间元素等于目标值，返回中间索引。

如果中间元素大于目标值，将 right 更新为 mid - 1，继续在左半部分查找。

如果中间元素小于目标值，将 left 更新为 mid + 1，继续在右半部分查找。

重复步骤2和3，直到 left 大于 right，此时目标元素不存在于数组中，返回 -1。

时间复杂度

二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。这是因为每次查找都将查找范围减半，因此算法的效率非常高。

java_34">java实现二分查找

代码如下：

java">/**
 * 二分查找
 */
public class BinarySearchExample {
    /**
     *
     * @param arr 有序数组
     * @param left 左边界
     * @param right 右边界
     * @param value 目标值
     * @return
     */
    public static int binarySearch(int[] arr, int left, int right, int value) {
        while (left <= right) {
            int mid = left + (right-left) / 2;
            if (arr[mid] == value) {
                // 找到目标元素，返回索引
                return mid;
            } else if (arr[mid] < value) {
                // 在右半部分继续查找
                left = mid + 1;
            }  else if (arr[mid] > value)  {
                // 在左半部分继续查找
                right = mid - 1;
            }
        }
        // 目标元素不存在
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 8, 12, 14, 20, 23, 29};
        int index = binarySearch(arr, 0, arr.length - 1, 20);
        System.out.println(index);
    }

}