二分查找算法

简介

二分查找是一种高效的搜索算法，特别适用于有序数组或列表。它通过将待查找区域一分为二，并缩小搜索范围，迭代地进行查找，直到找到目标元素或确定目标元素不存在为止。这种算法的时间复杂度是O(log n)，相比线性搜索等算法更加高效。

算法步骤

• 1. 初始化： 确定搜索范围的起始点low和结束点high。
• 2. 迭代： 计算中间点mid，检查中间点的元素与目标元素的关系。
  • 如果中间元素等于目标元素，则返回中间元素的索引。
  • 如果中间元素大于目标元素，则将搜索范围缩小为左半部分，即high = mid - 1。
  • 如果中间元素小于目标元素，则将搜索范围缩小为右半部分，即low = mid + 1。
• 3. 终止条件： 重复步骤2直到找到目标元素或搜索范围为空。

Java示例

public class BinarySearch {
    
    /**
     * 二分查找算法
     *
     * @param array   有序数组
     * @param target  要查找的目标元素
     * @return        目标元素的索引，如果不存在则返回-1
     */
    public static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;

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

            if (array[mid] == target) {
                return mid; // 目标元素找到
            } else if (array[mid] > target) {
                high = mid - 1; // 缩小搜索范围为左半部分
            } else {
                low = mid + 1; // 缩小搜索范围为右半部分
            }
        }

        return -1; // 目标元素不存在
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 5;

        int result = binarySearch(sortedArray, target);

        if (result != -1) {
            System.out.println("目标元素 " + target + " 的索引是 " + result);
        } else {
            System.out.println("目标元素 " + target + " 不存在");
        }
    }
}

性能分析

• 时间复杂度： 二分查找的时间复杂度为O(log n)，其中n是数组的长度。这是由于每次迭代都将搜索范围缩小为原来的一半。
• 空间复杂度： 二分查找的空间复杂度为O(1)，因为算法只需要常量级的额外空间。

总结

二分查找是一种高效的搜索算法，特别适用于有序数组或列表。通过将搜索范围一分为二，算法能够迅速定位目标元素，具有较低的时间复杂度。在实际应用中，二分查找常用于搜索、排序等场景，是编程中的常见算法之一。