[leetCode] 35. Search Insert Position

🎆 Description

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:

Input: nums = [1,3,5,6], target = 0
Output: 0

Example 5:

Input: nums = [1], target = 0
Output: 0

🎇 Solution

var searchInsert = function(nums, target) {
    let first = 0;
    let last = nums.length - 1;
    let mid;
    while (first <= last) {
        mid = Math.floor((last + first) / 2);
        if (nums[mid] ===  target) {
            return mid;
        } else if (nums[mid] < target) {
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }
        return first;
   }

이전 문제와 비슷한 풀이 방법을 썼다.
헷갈렸던 부분은 해당 인덱스에 타겟숫자가 없으면 있어야 하는 인덱스를 반환해야 하는 것이었다.

이 부분은 target과 mid값을 계속해서 크기 비교를 하기 때문에, 더 이상 이동할 인덱스가 없어 first와 last값이 같아진다면 결국 first값을 그냥 리턴하면 되었다.

중간지점, 첫번째와 마지막 값을 정하는 방법은 다양하기 때문에 예시로 그림을 그려가면서 한번 이해를 해보는 것이 중요한 것 같다.

Reference

• https://leetcode.com/problems/search-insert-position/submissions/