搜索插入位置（35）

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例

输入: [1,3,5,6], 5 输出: 2

输入: [1,3,5,6], 2 输出: 1

输入: [1,3,5,6], 7 输出: 4

输入: [1,3,5,6], 0 输出: 0

算法

遍历

export const searchInput = (nums, target) => {
	for (let i = 0; i < nums.length; i++) {
		if (nums[i] >= target) return i;
	}
	return nums.length;
};

二分查找

使用二分查找，只要是左端点移动时，将左端点移动的值记录在变量minStart中，如果找到值target则直接返回，否则从minStart开始依次向后寻找插入的位置

export const searchInput = (nums, target) => {
	let [index, isFind] = binarySearch(nums, target);
	if (isFind) return index;
	while (index < nums.length && nums[index] < target) {
		index++;
	}
	return index;
};
const binarySearch = (nums, target) => {
	let start = 0,
		end = nums.length - 1;
	let minStart = 0;
	while (start <= end) {
		const mid = ~~((start + end) / 2);
		if (nums[mid] < target) (start = mid + 1) && (minStart = mid);
		else if (nums[mid] > target) end = mid - 1;
		else return [mid, true];
	}
	return [minStart, false];
};

二分查找

题目分两种情况：

• 如果nums中有target则返回下标
• 如果nums中找不到target，则返回一个插入位置，即第一个比target大的值的位置

所以题目等于——“返回一个大于等于target的位置”

所以我们将nums[mid]>=target的情况下（即移动右端点到中点时），将移动后的右端点的位置保存在变量index中，（也等于将无限趋近target且大于target的值保存在index中），待跳出循环（即start>end时）返回这个变量index作为结果

index默认为nums.length可以免去边界判断，即当target大于nums中所有值时返回最后一个位置

export const searchInput = (nums, target) => {
	let start = 0,
		end = nums.length - 1;
	let index = nums.length;
	while (start <= end) {
		const mid = ~~((start + end) / 2);
		if (nums[mid] >= target) {
			index = mid;
			end = mid - 1;
		} else {
			start = mid + 1;
		}
	}
	return index;
};