给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
为 无重复元素 的 升序 排列数组-104 <= target <= 104
https://leetcode.cn/problems/longest-palindromic-substring/?favorite=2cktkvj
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
// 二分查找的条件:1.有序 2.有 index
var searchInsert = function(nums, target) {
let l = nums.length; // 获取 nums 的数组
let left = 0; // 定义左指针初始值
let right = l-1; // 定义右指针初始值
let ans = 4; // 定义返回值初始值,避免 target 大于数组中的所有值,不会走到 while 循环中的 if 条件,如果这里不定义初始值 4,则需要在 else 里也重新赋值 ans = mid+1
while(left<=right){
let mid = left+(right-left>>1); // 定义二分中间值
// 当目标元素小于等于中值,则返回当前中值的位置
if(target<=nums[mid]){
right = mid-1;
ans = mid;
}else{
// 否则中值位置+1,这时候 ans=mid+1
left = mid+1
}
}
return ans
};