leetcode editorial - Binary Search

영어 다까먹엇다 해석이라도 하자..

정확한 target 찾기

Step1
전체 범위를 두 덩어리로 나눠서 탐색 구역으로 설정합니다.
이 시작과 끝점은 보통 left, right로 이름을 붙이는데, 이 둘은 while의 범위로 사용되곤 합니다. 이러한 방식을 이용해 이 범위를 모두 검수했을 때 혹은 내부에서 지정된 조건을 통해 loop를 끝낼 수 있습니다.

Step2
중간 지점을 pivot으로 설정해 두 범위로 나누고, 주어진 target과 비교해 만일 nums[pivot]이 target보다 크다면, 이 범위를 더이상 검사하지 않도록 합니다.

• nums[mid] == target
  -잘 찾았넹. 반환해도 되겠음.
• nums[mid] < target
  - 이 배열은 정렬되어 있음을 보장 받았으므로, left 범위의 탐색구역(왼쪽부터 시작하는 절반)이 target보다 모두 작음을 보장받는다. 그러므로 left를 mid + 1로 당겨서 더이상 필요없는 부분을 탐색하지 않도록 한다.
• nums[mid] > target
  - 위와 같은 의미로, 오른쪽 절반이 target보다 큰것을 보장 받았으니 right = mid + 1로 옮겨 검수가 필요 없는 부분을 잘라내자.
  

시간 복잡도는 O(log n)

• 전체 탐색 범위가 시행 시마다 반으로 줄어든다.

공간 복잡도는 O(1)

• 루프를 도는 동안 걍 3개의 인덱스만 필요하니까용

상한선

target이 들어갈 수 있는 가장 오른쪽 idx 찾기

엥? 이러면 pivot을 어떻게 잡아야할까?

이런 케이스에서
nums[mid] < target이라면 left = mid + 1;
nums[mid] == target 이라면 left = mid + 1; 추가할 위치가 mid보다 우측에 있다는거니까???