1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

'''

1. 숫자들이 오름차순으로 정렬된 리스트와 타겟 넘버가 주어질 때, 리스트에서 타겟 넘버가 삽입될 
   인덱스를 구하는 문제.



2. 이진탐색을 구현할 때 주목해야 할 부분들
1) m = (s+e)//2
- 범위 내 수의 개수가 짝수 -> s에서 m까지의 개수와 m+1부터 e까지의 개수가 같다. 
- 범위 내 수의 개수가 홀수 -> s에서 m까지의 개수가 m+1부터 e까지의 개수보다 하나 많다.

2) while s < e:
- 루프는 s==e가 된 상태에서 종료된다.

3) if nums[m] < target: s=m+1
- 이진탐색에서 제일 중요한 조건식 쓰기. 여기서 생각해야 할 게, 여기서 써야 하는 조건식은 결국
  'target이 s ~ m 구간에 속하는 수인가? m+1 ~ e 구간에 속하는 수인가?'를 묻는 조건식이고,
  nums[m]이라는 값을 사용해서 조건식을 쓰고자 한다면 결국 써야 하는 조건식은
  'if nums[m] >= target' 또는 'if nums[m] < target'임.
  여기서 써야하는 조건식의 의미에 대한 이해가 부족하면, nums[m]==target인 경우를 어떻게 처리해야 할지
  판단이 어려워져서 코드가 조금 길어지고 복잡한 예외처리를 해야 하는 경우가 생길 수 있음.
  (길어져봐야 서너 줄 정도에 불과하긴 하나 그 서너 줄 없이 정확히 작동하는 코드를 쓸 수 있다는 점.)
  특히 문제가 만약 이 문제처럼 '타겟 넘버가 리스트에 없다면 타겟 넘버가 삽입돼야 할 위치를 리턴하라'
  는 문제라면, '타겟 넘버가 s ~ m 영역보다 큰 수라면 다음 루프는 m+1 ~ e 영역을 탐색'이라는 식으로
  코드를 쓰면 '루프가 끝나는 지점(s==e)이 곧 타겟 넘버가 삽입돼야 할 지점'이라는 내용이 간단히 구현됨.
  이 부분을 파악 못하면 코드가 이것보다 다소 길어질 것.  

'''

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        s, e = 0, len(nums)-1
        while s < e:
            m = (s+e)//2
            if nums[m] < target:
                s = m+1
            else:
                e = m
        return e + ( 1 if target > nums[e] else 0)