数据结构与算法之二分查找算法详解（Java实现）

九转成圣

发布于 2024-12-02 09:59:07

1.2K00

代码可运行

文章被收录于专栏：csdncsdn

运行总次数：0

代码可运行

二分查找算法详解（Java实现）

二分查找（Binary Search）是一种非常高效的查找算法，它在有序数组或有序列表中通过反复将搜索范围分为两半来查找目标元素。由于每次查找都将规模减半，所以它的时间复杂度是 O(log n)，比线性查找 O(n) 要高效得多。

1. 二分查找的基本原理

二分查找要求输入数据必须是有序的（升序或降序），并且通过以下步骤进行查找：

确定中间位置：计算数组的中间索引 mid，即 mid = (low + high) / 2，其中 low 和 high 分别是数组的起始和结束索引。
比较元素
- 如果 target == arr[mid]，则找到了目标元素，返回该索引。
- 如果 target < arr[mid]，则目标元素可能在 mid 左侧，将 high 更新为 mid - 1。
- 如果 target > arr[mid] ，则目标元素可能在 mid 右侧，将 low 更新为 mid + 1。
重复以上步骤，直到找到目标元素或者确定目标元素不存在。

2. 二分查找的代码实现

2.1 标准二分查找（适用于升序数组）

以下是标准的二分查找算法实现，它查找一个升序排列的数组中的目标值。

public class SearchBinary {
    public static void main(String[] args) {
        int[] array = {3, 14, 22, 30, 31, 38, 41, 44};
        int target = 14;
        int search = search(array, target);
        System.out.println("search = " + search);
        target = 41;
        search = search(array, target);
        System.out.println("search = " + search);
        target = 33;
        search = search(array, target);
        System.out.println("search = " + search);
    }

    private static int search(int[] array, int target) {
        int low = 0;
        int hight = array.length - 1;
        while (true) {
            int mid = (low + hight) / 2;
            if (low > hight) {
                return -1;
            }
            if (target == array[mid]) {
                return mid;
            }
            if (target < array[mid]) {
                hight = mid - 1;
            }
            if (target > array[mid]) {
                low = mid + 1;
            }
        }
    }
}

运行结果

search = 1
search = 6
search = -1

第一次查找

value	3	14	22	30	31	38	41	44
index	0	1	2	3	4	5	6	7
	low			mid				hight

第二次查找

value	3	14	22	30	31	38	41	44
index	0	1	2	3	4	5	6	7
	low	mid	hight

2.2 代码解释：

low 和 high 表示当前查找范围的起始和结束索引。
在 while 循环中，我们通过计算 mid 索引来获取中间元素。
根据比较 arr[mid] 和目标值 target 的结果，调整 low 或 high，逐步缩小查找范围，直到找到目标元素或搜索区间为空（即 low > high）。
如果找到目标元素，返回目标元素的索引；如果没有找到，则返回 -1。

2.3 二分查找的时间复杂度

二分查找的时间复杂度是 O(log n)，其中 n 是数组的长度。每次查找操作都会将问题规模减半，直到找到目标元素或者区间为空为止。因此，二分查找比线性查找（O(n)）要高效得多，尤其是在大数据集上。

3. 改进的二分查找（用于查找插入位置）

有时，我们不仅仅需要查找某个元素，还需要找到一个目标元素在数组中的插入位置。在这种情况下，我们可以稍作修改，找到第一个不小于目标元素的位置。

3.1 查找插入位置的实现

public class BinarySearch {

    // 查找插入位置的方法
    public static int findInsertPosition(int[] arr, int target) {
        int low = 0;
        int high = arr.length;

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (arr[mid] < target) {
                low = mid + 1; // 插入位置在右半部分
            } else {
                high = mid; // 插入位置在左半部分
            }
        }

        return low; // 返回插入位置
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17};
        int target = 8;

        int position = findInsertPosition(arr, target);
        System.out.println("目标元素 " + target + " 应该插入的位置是 " + position);
    }
}

3.2 代码解释：

这个方法返回的是目标元素应该插入的位置。它采用了类似于二分查找的策略，不同之处在于我们在比较 arr[mid] 和目标值后，将 high 设置为 mid，而不是 mid - 1，这样可以保证最终 low 指向的就是目标元素的插入位置。
如果目标元素已经存在，返回的插入位置就是目标元素的索引。