[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

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

Solution 1. 이진 탐색(Binary Search)

public int searchInsert(int[] nums, int target) {

    int start = 0;
    int end = nums.length-1;

    while(start <= end){
        int mid = start + (end-start)/2;
        if(target == nums[mid]){
            return mid;
        }else if(target > nums[mid]){ // 같은 걸 찾기위해 줄여야함
            start = mid+1;
        }else{
            end = mid-1;
        }
    }
    return start;
}

정렬되어 있는 배열에서 원하는 값을 찾기 위해 이진 탐색(Binary Search)을 이용할 수 있습니다.

검색 범위를 지정할 두개의 포인터를 두고 가운데 값(mid)을 스캔한 후 찾는 값(target)이 중간값보다 작으면 스캔범위를 포인터를 앞으로 옮기고 아니면 뒤쪽을 스캔하는 것을 반복합니다.

• 시간복잡도 : O(logN)
• 공간복잡도 : O(1)

Reference

Search Insert Position - LeetCode