문제를 이해하고 있다면 바로 풀이를 보면 됨
전체 코드로 바로 넘어가도 됨
마음대로 번역해서 오역이 있을 수 있음

Problem

별개의 정수가 정렬된 배열과 목표 값이 주어지고, 만약 그 목표가 발견되면 그 인덱스를 반환해라. 그렇지 않다면 순서대로 삽입되었을때 인덱스를 반환해라.
당신은 O(log n)의 시간복잡도를 갖는 알고리즘을 작성해야한다.

Example

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

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

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

Constraints

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums는 오름차순으로 정렬된 별개의 값이 포함한다.
• -10^4 <= target <= 10^4

Solved

O(log n)의 시간복잡도로 문제를 해결하라고 해서, 이진탐색을 사용해서 문제를 해결해야한다.

정수 L, R, M을 선언하고, 각각 0, nums.length - 1, 0을 할당한다.

int L = 0;
int R = nums.length - 1;
int M = 0;

while문으로 L이 R보다 작거나 같을때까지 반복한다.

while(L <= R){

}

while문 안에서 M에 (L + R) / 2를 할당한다. (이진탐색에서 가운데 값을 지정할때 무조건 하는 것)
그리고 if문을 통해 nums[M]과 target이 같다면 M을 할당하고, nums[M]이 target보다 작으면 L에 M + 1을 할당하고, nums[M]이 target보다 크다면 R에 M - 1을 할당한다.

while(L <= R){
  M = (L + R) / 2;
  
  if(nums[M] == target){
    return M;
  }else if(nums[M] < target){
    L = M + 1;
  }else if(nums[M] > target){
    R = M - 1;
  }
}

그리고 target이 없는 경우에 삽입되는 인덱스를 반환해야해서 while문을 빠져나왔을때 nums[M]이 target보다 작거나 같으면 M + 1을 반환한다.

if(nums[M] <= target){
  return M + 1;
}

마지막에 M을 반환한다.

return M;

All Code

class Solution {
    public int searchInsert(int[] nums, int target) {
        int L = 0;
        int R = nums.length - 1;
        int M = 0;
        
        while(L <= R){
            M = (L + R) / 2;

            if(nums[M] == target){
                return M;
            }else if(nums[M] < target){
                L = M + 1;
            }else if(nums[M] > target){
                R = M - 1;
            }
        }

        if(nums[M] <= target){
            return M + 1;
        }

        return M;
    }
}