[LeetCode/Easy] 35. Search Insert Position

1. Input

1) int[] nums

2) int target

 

2. Output

1) nums에 target을 찾아서 그 인덱스를 반환

2) nums에 target이 없다면 target이 들어가게 될 인덱스를 반환

 

3. Constraint

1) 1 <= nums.length <= 10^4

2) - 10^4 <= nums[i] <= 10^4

3) nums에는 중복요소가 없고 오름차순으로 정렬되어 있다.

4) - 10^4 <= target <= 10^4

5) O(log n)의 복잡도를 갖는 알고리즘으로 작성해야 한다.

 

4. Example

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

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

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

 

5. Code

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

- 100%, 93%