二分查找进阶：查找不存在的元素（图解）

二分查找进阶：查找不存在的元素（图解）

引用

CSDN

1.

https://blog.csdn.net/hkj887tg/article/details/137492999

二分查找是一种在有序数组中查找特定元素的高效算法。本文将从基础概念出发，深入讲解如何在二分查找中处理目标元素不存在的情况，并通过图解和代码示例帮助读者理解这一算法的进阶应用。

二分查找基础

二分查找算法通过将数组对半分，并根据元素与中间元素的关系来递归地缩小搜索范围来工作。具体步骤如下：

1. 初始化左边界（low）和右边界（high），分别为数组的第一个和最后一个索引。
2. 计算中间索引（mid）为 (low + high) / 2（向下取整）。
3. 将目标元素与数组的中间元素进行比较：

• 如果等于，则返回中间索引。
• 如果小于，则将 high 更新为 mid - 1。
• 如果大于，则将 low 更新为 mid + 1。

4. 重复步骤 2 和 3，直到 low 大于或等于 high。
5. 如果 low 大于 high，则返回 -1，表示元素不存在。

使用前提

• 数组必须已排序：二分查找算法要求数组必须已按升序或降序排序。
• 元素可比较：数组中的元素必须可比较，以便可以确定它们是相等、大于或小于其他元素。
• 数组大小已知：算法需要知道数组的大小，以便计算中间索引。
• 元素唯一或允许重复：如果数组中允许重复元素，则算法可能会返回第一个找到的匹配元素的索引，而不是所有匹配元素的索引。

代码模板

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int target = 11;
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("Element not found.");
        } else {
            System.out.println("Element found at index " + result);
        }
    }
}

查找不存在的元素

在实际应用中，我们经常会遇到目标元素不存在的情况。这时，我们需要对基础的二分查找算法进行改进，使其能够返回最接近目标值的元素。

图解

初始化：low = 0，high = array.size()-1

因为array[mid] > target，更新high = mid - 1

array[mid] < target，更新low= mid+1,注意跳出循环条件，需要low>high，而此时low = high，所以还进入循环。

array[mid] < target，更新low = mid + 1。此时low > high，跳出循环。

且中间没有出现array[mid] == target，没有return，就说明没有找到目标

在没有找到目标时，返回比目标值小的最接近目标值的元素。其下标为基础算法跳出循环时的low减1。

代码

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
        int target = -1;
        int index = binarySearchClosestOrTarget(arr, target);
        if (index != -1) {
            if (arr[index] == target) {
                System.out.println("目标值 " + target + " 在索引 " + index + " 处找到。");
            } else {
                System.out.println("最接近目标值 " + target + " 的元素在索引 " + index + " 处，值为 " + arr[index]);
            }
        } else {
            System.out.println("未找到目标值 " + target);
        }
    }
    public static int binarySearchClosestOrTarget(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        int closestIndex = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
                closestIndex = mid;
            } else {
                high = mid - 1;
            }
        }
        // 如果未找到目标值，则返回最接近目标值的元素的索引
        if (closestIndex == -1) {
            return low - 1;
        }
        // 如果找到了目标值，则返回目标值的索引
        return closestIndex;
    }
}