문제링크

• target 정수의 크기를 고려하여, 정수형 배열의 알맞은 위치에 삽입하는 문제이다.

풀이

1. 브루트 포스로 탐색 (O(n))

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

2. 이진 탐색 (O(logn))

코드 출처 : https://beccacatcheserrors.tistory.com/9

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

        // 이진탐색
        int first = 0;
        int last = nums.length - 1;
        int mid;

        while(first <= last){
            mid = (first + last) / 2;
            if(target == nums[mid])
                return mid;
            else if(target < nums[mid])
                last = mid -1;
            else
                first = mid + 1;
        }
        return first;

    }
}

• 술자리에서 병뚜껑의 숫자를 맞추는 게임을 생각하면 좋다.
• 1 ~ 60 중의 숫자를 찾는다면, 가운데인 30을 기준으로 up, down을 확인하며 mid값을 갱신해 나가는 방식이다.