[알고리즘 / 초급] Binary Search Insert

Leetcode의 다음 문제에 대한 풀이입니다

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

 

문제

 정렬된 배열과, 목표값을 가지고 만약 목표값이 배열안에 있으면 그 인덱스를 return하고, 없다면 target값이 들어가기 적합한 위치의 인덱스를 return

예시

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

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

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

 

조건

Time Complexity : O(log n)

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums는 각기 고유한 값을 가지며, 오름차순 정렬 되어있음
• -104 <= target <= 104

 

풀이

  O(log n)를 만족시키려면 Binary Search를 이용해야 합니다. Memory를 아끼려면 Array(List)를 계속해서 다시 만들지 말고, index값을 이용해서 메모리를 아끼도록 합시다

public int searchHelper(int start, int end, int target, int[] nums){

//베이스 케이스 1. start와 end 인덱스가 같다면 멈춤 

//케이스 2. nums[start] 값이 target과 같다면, start return

//케이스 3. nums[end] 값이 target과 같다면, end return

//케이스 4. nums[(start+end)/2] 값이(중앙값) target과 같다면, (start+end)/2 return

//여기선 recursion

// nums[(start+end)/2]> target 이면 중간기준 왼쪽에서 search

// nums[(start+end)/2]< target 이면 중간기준 오른쪽에서 search

//모든 경우에 맞지 않다면 0

}

위의 Helper 기능을 이용합니다. 

 

여기서 자바의 속성을 이용할 수 있습니다. 자바의 int의 경우 2.xxyy로 계산되는 값은 2로 계산됩니다.

예를 들어 int 3/2 -> 1.5 -> 1로 반환 됩니다.

 

답은 여기에

class Solution {
    public int searchInsert(int[] nums, int target) {
      return searchHelper(0, nums.length-1, target,nums);
    }
    
        public int searchHelper(int start, int end, int target, int[] nums){

        if(start==end){
            if(nums[start]<target){
                return ++start;
            }
            return start;
        }
        if (nums[start]==target){
            return start;
        }
        if(nums[end]==target){
            return end;
        }

        if(nums[(start+end)/2] == target){

            return (start+end)/2;
        }

        if(nums[(start+end)/2]>target){

            return searchHelper(start,(start+end)/2, target, nums);
        }
        if(nums[(start+end)/2]<target){

            return searchHelper((start+end)/2+1,end, target, nums);
        }


        return 0;
    
    }
}

 

저보다 잘하시는 분도 있겠지만, 위의 코드로 했을때 성적은 다음과 같습니다.

메모리사용

 약 상위 55% 정도의 메모리 사용이라고 보면 될 것 같습니다.