[LeetCode] 35. Search Insert Position

轉自LeetCode

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

<Solution>

這題就用 binary search 來做

那注意一個地方是

當 nums[mid] > target 的時候，right = mid 而不是 right = mid - 1

這樣當 target 不在 nums 裡，且又沒超過 nums 的最大最小值

就返回 right

code 如下
c++

	class Solution {
	public:
	int searchInsert(vector<int>& nums, int target) {
	if(nums.empty() || target < nums.front()) {
	return 0;
	}
	else if(target > nums.back()) {
	return nums.size();
	}
	int left = 0, right = nums.size() - 1;
	while(left < right) {
	int mid = (left + right) / 2;
	if(nums[mid] == target) {
	return mid;
	}
	else if(nums[mid] < target) {
	left = mid + 1;
	}
	else {
	right = mid;
	}
	}
	return right;
	}
	};

view raw searchInsertPosition.cpp hosted with ❤ by GitHub

這邊有統整一下 binary search 使用的一些情境，可以拿來參考

kotlin

	class Solution {
	fun searchInsert(nums: IntArray, target: Int): Int {
	var left = 0
	var right = nums.size
	var mid = 0
	while(left < right) {
	mid = left + (right - left) / 2
	if(nums[mid] < target) {
	left = mid + 1
	} else {
	right = mid
	}
	}
	return right
	}
	}

view raw search_insert_position.kt hosted with ❤ by GitHub