二分搜索算法

目录

一. 算法思想

二. 二分搜索的复杂度

三. 二分搜索的使用场景

四. 代码模板

一. 算法思想

1. 前提条件：二分搜索算法要求待搜索的数组必须是有序的。通常是升序排列，但也可以是降序排列。

2. 基本步骤：

   • 初始化：确定搜索范围的起始点和结束点，通常是数组的第一个元素和最后一个元素。
   • 循环：在每次循环中，计算搜索范围的中间点。
   • 比较：将中间点的值与目标值进行比较：
     • 如果中间点的值等于目标值，则搜索成功，返回中间点的索引。
     • 如果中间点的值小于目标值，则说明目标值在中间点的右侧，将搜索范围缩小到中间点的右侧。
     • 如果中间点的值大于目标值，则说明目标值在中间点的左侧，将搜索范围缩小到中间点的左侧。
   • 结束条件：如果搜索范围的起始点大于结束点，则说明目标值不在数组中，搜索失败，返回特定的失败标志（如 -1）。

二. 二分搜索的复杂度

• 时间复杂度：O(log n)，其中 n 是数组的长度。每次查找都将问题的规模减半，因此执行的步骤数量与输入规模的对数成正比。
• 空间复杂度：O(1)（如果是非递归实现）或者 O(log n)（如果是递归实现，主要是由于递归调用栈的占用）。

三. 二分搜索的使用场景

二分搜索不仅可以用于查找单个元素，还可以进行一些变种操作，例如：

• 查找第一个出现的位置：在数组中查找目标值第一次出现的索引。
• 查找最后一个出现的位置：在数组中查找目标值最后一次出现的索引。
• 查找大于等于目标值的最小值：可以用来解决一些与插入位置相关的问题。
• 查找小于等于目标值的最大值。

四. 代码模板

int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

// 左边界
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    if (left < 0 || left >= nums.length) {
        return -1;
    }
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

// 右边界
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 由于 while 的结束条件是 right == left - 1，且现在在求右边界
    // 所以用 right 替代 left - 1 较为好记一些
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}

以上便是二分搜索算法模板的核心代码。二分搜索是一种简单而高效的查找算法，尤其适用于需要频繁查找的场景。其应用场景包括但不限于数值查找、字符串查找等，广泛用于计算机科学及相关领域中。理解二分搜索的原理和实现，不仅能够提升编程能力，还能为算法学习打下良好的基础。