二分查找三种模板
2021-01-17 本文已影响0人
whelm
leetcode 35 题
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
模板 1:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
// 比较第一个和最后一个
if(nums[0] > target) {
return 0;
}
if(nums[nums.length - 1] < target) {
return nums.length;
}
// 需要查找
var left = 0;
var right = nums.length;
while(left < right) {
var mid = Math.floor((left + right)/2);
if(nums[mid] === target) {
return mid;
}
if(nums[mid] > target) {
// 向左查找
right = mid - 1;
} else {
// 向右查找
left = mid + 1;
}
// 最后一次查找情况:(left === right === mid)
// 如果不符合条件则会变为 left > right 循环中止
}
// 循环中止后考虑情况
return left;
};
模板 2:
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
// 比较第一个和最后一个
if(nums[0] > target) {
return 0;
}
if(nums[nums.length - 1] < target) {
return nums.length;
}
// 需要查找
var left = 0;
var right = nums.length;
while(left < right) {
var mid = Math.floor((left + right)/2);
if(nums[mid] === target) {
return mid;
}
if(nums[mid] > target) {
// 向左查找
right = mid;
} else {
// 向右查找
left = mid + 1;
}
// 最终一次查找情况:(left < right 并相邻, mid === left)
// 如果不符合条件则会变为 left === right 循环中止
}
// 循环中止后考虑情况
return left;
};