二分查找过程描述和代码实现、二分查找插入点篇11

二分查找过程描述和代码实现、二分查找插入点篇11

引用

CSDN

1.

https://m.blog.csdn.net/weixin_44262492/article/details/145495156

1、二分查找

1.1、相关定义和描述

定义：一种基于分治策略的高效搜索算法。利用数据有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

问题描述：给定一个长度为 n的数组 nums ，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回-1。

1.2、过程描述

先初始化指针i= 0和考，分别指向数组首元素和尾元素，代表搜索区间【0，n-】。请注意，中括号表示闭区间，其包含边界值本身。

1.3、代码实现

/* 二分查找（双闭区间） */
int binarySearch(int[] nums, int target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    int i = 0, j = nums.length - 1;
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

1.4、复杂度分析

时间复杂度：O(log n)：在二分循环中，区间每轮缩小一半，循环次数为log 2 n）。

空间复杂度： O(1）：指针i和j使用常数大小空间

2、二分查找插入点

二分查找搜索目标元素，解决许多变种问题，比如搜索目标元素的插入位置。

2.1、无重复元素的情况

定一个长度为n的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target 插入数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返回插入后 target 在数组中的索引.

/* 二分查找插入点（无重复元素） */
int binarySearchInsertionSimple(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            return m; // 找到 target ，返回插入点 m
        }
    }
    // 未找到 target ，返回插入点 i
    return i;
}

2.2、存在重复元素情况

在上一题的基础上，规定数组可能包含重复元素，其余不变。

/* 二分查找插入点（存在重复元素） */
int binarySearchInsertion(int[] nums, int target) {
    int i = 0, j = nums.length - 1; // 初始化双闭区间 [0, n-1]
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target) {
            i = m + 1; // target 在区间 [m+1, j] 中
        } else if (nums[m] > target) {
            j = m - 1; // target 在区间 [i, m-1] 中
        } else {
            j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
        }
    }
    // 返回插入点 i
    return i;
}