二分查找算法详解与实战案例

1. 二分查找

• 在一个长度为 n 的数组中要查找一个数字，逐一扫描数组中的每个数字，需要 O(n) 的时间
• 如果数组是排序的，那么可以采用二分查找算法进行优化，采用分治思想，将数组分为三个区域，判断中间值是否命中，如果没命中，继续在其中的一个区域继续进行分治查询

2. LCR 068. 搜索插入位置

题目描述

给定一个排序的整数数组 nums 和一个整数目标值 target，请在数组中找到 target，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

示例 1： 输入：nums = [1,3,5,6], target = 5 输出：2

示例 2： 输入：nums = [1,3,5,6], target = 2 输出：1

示例 3： 输入：nums = [1,3,5,6], target = 7 输出：4

示例 4： 输入：nums = [1,3,5,6], target = 0 输出：0

示例 5： 输入：nums = [1], target = 0 输出：0

提示： 1 <= nums.length <= 10^4 -10^4 <= nums[i] <= 10^4 nums 为无重复元素的升序排列数组 -10^4 <= target <= 10^4

解题思路

1. 审题：输入一个升序排序的整数数组和一个目标值 target，要求在数组中查找是否存在目标值，如果存在返回该目标值在数组中的下标位置；如果不存在，返回插入该数值应该所在的位置。
2. 解题：题目要求使用二分查找法。
   • 使用左右指针 left、right 分别标记查找范围，取中间值 mid。
   • 如果 mid 下标值等于目标值，则返回 mid。
   • 如果 mid 值大于目标值，且 mid-1 小于目标值，则查找到插入位置，如果 mid 已经是下标 0 了，也直接返回。
   • 如果 mid 值小于目标值，继续在后半部分查找，left = mid + 1。
   • 如果还是没有找到，说明数组中所有元素都小于目标值，应该插入到数组最末尾端。

代码实现

int searchInsert(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    int mid = 0;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] > target) {
            if (mid == 0 || nums[mid - 1] < target) {
                return mid;
            }
            right = mid - 1;
        }  {
            left = mid + ;
        }
    }
     nums.();
}