[LeetCode] 35. Search Insert Position

[Medium] 35. Search Insert Position

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

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.

Example 1

Input: [1,3,5,6], 5
Output: 2

Example 2

Input: [1,3,5,6], 2
Output: 1

문제 설명

단순히 Insert position을 구하는 문제로, 정렬된 배열에서 주어진 값이 어느 위치에 들어가야 하는지 찾는 문제다.

나의 풀이

O(N) 단순 배열을 for loop으로 순회하며, target보다 nums[i]의 값이 크거나 같을 경우 i를 리턴한다.

class Solution {
    public int searchInsert(int[] nums, int target) {
        int i;
        for(i = 0; i < nums.length; i++){
            if(target <= nums[i]){
                return i;
            }

        return i;
    }
}

베스트 풀이

아니나 다를까 이걸 더 효율화 한다고 사람들은 binary search를 통해 index를 찾는다. O(logN)의 시간 복잡도를 가진다.

public int searchInsert(int[] A, int target) {
    int low = 0, high = A.length-1;
    while(low<=high){
        int mid = (low+high)/2;
        if(A[mid] == target) return mid;
        else if(A[mid] > target) high = mid-1;
        else low = mid+1;
    }
    return low;
}