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
解题思路
- 审题:输入一个升序排序的整数数组和一个目标值 target,要求在数组中查找是否存在目标值,如果存在返回该目标值在数组中的下标位置;如果不存在,返回插入该数值应该所在的位置。
- 解题:题目要求使用二分查找法。
- 使用左右指针 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.();
}


