Binary Search

[LogicBaron]

ProblemList

• https://leetcode.com/problems/maximum-number-of-groups-with-increasing-length/description/ hard
  • hard to get idea of satisfy certain group number.

[LogicBaron]

Binary search 에서 설정에 따른 flow 를 좀 알아봅시다.

binary search 는 기본적으로 mid = (left+right)/2 값을 통해 target 값을 찾아가는 과정인데.. 설정에 따라 몇가지 처리가 가능하다.

1. v[mid] == target 일 때 고려하기
2. (left+right)/2 값은 언제나 1 차이나면 결국 left 로 수렴한다. -> left = mid 를 사용하면 while 구문을 특별히 바꾸지 않는 이상 수렴 못시킴. (mid, mid+1) -> (mid, mid+1)... -> left 는 어지간하면 mid+1 을 써줘야함.

1. 제일 작은 target 값 index 찾기

while (left<right) {
    mid = (left+right)>>1;
    if (v[mid] < target) left = mid+1;
    else right = mid; 
}
return v[l]; // same as v[r];

제일 작은 target 값 index 를 찾는다. target 값이 존재하지 않을 경우, target 값보다 작으면서 가장 큰 값의 index 를 찾는다. -> while(left<=right) 구문은 쓸 수 없음. right=mid, left=mid 에서 끊임없이 돌게 됨. -> if (v[mid]<=target) left=mid; else right=mid-1;

2. 제일 큰 target 값 index 찾기

while (left<=right) {
    mid = (left+right)>>1;
    if (v[mid] <= target) left = mid+1; // 여기가 핵심임. 같은 경우에도 left 를 올려쳐주기
    else right = mid-1; // [3,4,5] 에서 4를 찾을때 left<right 로 종료하면 5에서 수렴해버림. left<=right 로 하고 4에서 수렴하도록.
}
return v[r];

가장 큰 target 값의 index 를 반환한다. target 값이 vector 내에 없을 경우 마찬가지로 target 보다 작은 값 중 가장 큰 값의 index 를 반환한다.