数据结构第24节 二分查找

时间：2024-07-14 20:48:54

二分查找（Binary Search），也被称为折半查找，是一种在有序数组中查找特定元素的高效算法。它的基本思想是将查找区间分为两部分，通过比较中间元素与目标值来决定下一步是在哪一半继续查找。

二分查找的步骤：

  1. 初始化：定义两个指针 left 和 right 分别指向数组的起始位置和结束位置。
  2. 循环条件：当 left <= right 时，继续执行以下步骤。
  3. 计算中间位置：mid = (left + right) / 2。为了避免整型溢出，通常使用 mid = left + (right - left) / 2 或者 mid = (left + right) >>> 1。
  4. 比较：比较数组中间位置的元素 arr[mid] 与目标值 target。
    • 如果 arr[mid] == target，则找到了目标值，返回 mid。
    • 如果 arr[mid] < target，则更新 left = mid + 1，因为目标值可能位于右侧子数组。
    • 如果 arr[mid] > target，则更新 right = mid - 1，因为目标值可能位于左侧子数组。
  5. 重复步骤3和4，直到找到目标值或者 left > right。
  6. 未找到：如果退出循环是因为 left > right，说明数组中不存在目标值，返回 -1 或者其他表示未找到的值。

Java 实现：

下面是一个简单的二分查找的Java实现示例：

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            // 防止(left + right)可能导致的溢出
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 目标值不在数组中
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 4;
        int result = binarySearch(arr, target);
        
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array");
        }
    }
}

时间复杂度：

二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。这是因为每次比较都会将搜索空间减半，直到找到目标值或搜索空间为空。

注意事项：

  • 数组必须是有序的。
  • 二分查找仅适用于静态数组，对于动态变化的数据结构，如频繁插入删除的列表，可能不是最佳选择。
  • 在处理边界条件和溢出时要小心，以避免潜在的错误。

在Java中优化二分搜索代码主要可以从以下几个方面进行：

  1. 防止整数溢出：在计算中间位置时，使用 (left + right) / 2 可能会遇到整数溢出的问题，尤其是在 left 和 right 均为较大的正整数时。解决这个问题的一种方法是使用 (left + right) >>> 1 或 left + (right - left) / 2 来计算中间位置。

  2. 减少不必要的计算：在循环内部，可以避免重复计算已经确定的值，比如 mid 的计算只应在每次循环开始时进行一次。

  3. 简化循环条件：确保循环终止条件是最简洁有效的形式。

  4. 处理边界情况：确保你的代码能够正确处理边界情况，比如空数组、单元素数组等。

下面是一个优化过的二分查找Java代码示例：

public class BinarySearch {
    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; // 防止溢出
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 目标值不在数组中
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 4;
        int result = binarySearch(arr, target);
        
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found in the array");
        }
    }
}

在这个版本中，我们使用了 left + (right - left) / 2 来避免整数溢出问题，并且循环条件和计算逻辑已经尽可能地简化和标准化。此外，我们还应该考虑是否需要处理数组为空的情况，这可以通过在循环之前添加一个检查来完成：

if (arr == null || arr.length == 0) {
    return -1;
}

最后，根据实际应用的需求，你可能还需要考虑以下几点：

  • 如果数组中有多个相同的元素，你可能需要修改算法来找到第一个或最后一个匹配项。
  • 如果你需要在没有找到目标值的情况下插入它，可以利用返回值来确定插入位置。
  • 对于非常大的数据集，考虑使用并行或分段的二分搜索算法，以提高性能。

为了进一步完善二分查找的代码，我们可以考虑以下几点：

  1. 处理特殊情况：例如，如果数组为空或null，应立即返回适当的结果。
  2. 寻找目标值的第一个或最后一个出现的位置：这对于有重复元素的数组特别有用。
  3. 查找目标值的插入位置：当目标值不存在于数组中时，返回其应该被插入的位置。

接下来，我们将分别针对这些场景提供代码示例。

1. 处理特殊情况

public static int binarySearch(int[] arr, int target) {
    if (arr == null || arr.length == 0) {
        return -1; // 或者返回一个特殊值，如 arr.length 表示目标值应插入数组末尾
    }
    int left = 0;
    int right = arr.length - 1;
    
    // ... 其他代码 ...
}

2. 查找目标值的第一个或最后一个出现的位置

假设数组可能包含重复的目标值，我们希望找到它的第一次出现或最后一次出现的位置。

第一次出现的位置
public static int findFirstOccurrence(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            right = mid - 1; // 继续在左边查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}
最后一次出现的位置
public static int findLastOccurrence(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            result = mid;
            left = mid + 1; // 继续在右边查找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return result;
}

3. 查找目标值的插入位置

当目标值不存在于数组中时，返回其应该被插入的位置。

public static int findInsertPosition(int[] arr, int target) {
    int left = 0;
    int right = arr.length;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

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

这些函数可以根据具体的应用场景进行调用，以满足不同的需求。

相关文章