[leetcode #35] Search Insert Position

Problem

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

Constraints:

・ 1 <= nums.length <= 10⁴
・ -10⁴ <= nums[i] <= 10⁴
・ nums contains distinct values sorted in ascending order.
・ -10⁴ <= target <= 10⁴

Idea

Time complexity를 O(logn)으로 풀어야 하므로 binary search를 이용하면 된다.

중간 index의 값에 따라 앞쪽 또는 오른쪽을 검색하면 되며, 하나의 값만 남았는데 target과 다를 경우 그 값의 크기에 따라 index를 그대로 리턴할지 아니면 1을 더한 index를 리턴한지 결정한다.

Solution

class Solution {
    int[] nums;

    public int searchInsert(int[] nums, int target) {
        this.nums = nums;    

        return findInsertPosition(0, nums.length-1, target);
    }

    private int findInsertPosition(int startIndex, int endIndex, int target) {
        if (startIndex >= endIndex) {
            if (nums[startIndex] < target)
                return startIndex+1;
            else
                return startIndex;
        }

        int mid = startIndex + (endIndex - startIndex) / 2;

        if (nums[mid] < target) {
            return findInsertPosition(mid+1, endIndex, target);
        } else if (nums[mid] > target) {
            return findInsertPosition(startIndex, mid-1, target);
        }

        return mid;
    }
}

Reference

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