리트 코드 35. Search Insert Position JAVA

문제

문제 해석

이진검색을 활용해서 문제를 해결하라라는 것
You must write an algorithm with O(log n) runtime complexity.
이 부분을 보니 Arrays.binarySearch()를 활용 할 수 없으며, 직접 이진 검색 메서드를 만들라는 문제같다.ㅏ

수도코드

    public int binarySearch(int[] n , int target){
        int end = n.length-1;
        int start = 0;

        while(start <= end)
            int mid = start + (end - start) /2;
            if(n[mid]< target)
                end = mid -1;
            else if (n[mid]< target)
                start =mid + 1;
            else
                return mid

        로직을 끝냈는데 아직도 반환하지 못했다면? ->start가 가리키는 값이 들어가야될 위치가 된다. JAVA에서는 이럴경우 음수로 하나 이전의 index를 반환해준다.
        return start ;    

    }

수도코드를 짯는데 얼추 코드가 완성이 되어있다.
이진 검색은 따로 구현해본 경험이 있어서 그런지 빠르게 구현할 수 있었다.
바로 코드로 확인해보자.

코드

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

        while(start <= end){
            int mid = start + (end - start) /2;
            if(n[mid]< target)
                start =mid + 1;
            else if (n[mid]> target)
                end = mid -1;
            else
                return mid;
        }
        return start ;

    }
}

코드를 보면 일단 중간 값을 찾는다.(mid)

• n[mid] 가 target 보다 작을 경우
  • start = mid +1 로 변경
• n[mid] 가 target 보다 클 경우
  • end = mid -1 로 변경하고 다시 루프를 돈다.

이렇게 루프를 계속 돌고 값을 찾지 못하면 그 때 start값을 반환한다.

회고

문제가 JAVA에 구현되어 있던 이진 검색 메서드를 구현하는 것이었다.
캠프에서 학습을 할 때 이미 구현해본 경험이 있어서 그런가 쉽고 빠르게 구현할 수 있었다.