[알고리즘] Binary Search

Bianry Search는 오름차순(또는 내림차순)으로 정렬된 배열에서 특정 값을 찾는 방법이다

로직의 핵심은 middle point를 선정하는데 있다.

특정 value A를 찾아야 되는 경우, middle을 찾고 value가 middle point보다 작거나 큰지 검사한다

작다면 middle point 보다 큰 값들은 모두 대상에서 제외되는 것이다

이러한 방식으로 매번 반절씩 후보군을 줄여나갈 수 있다

 

기본적인 코드는 다음과 같다

left, right를 정해주고 Loop안에서 middle point를 지속적으로 바꿔주며 target을 찾는다

 

 

 

예시1. 33 Search in Rotated Sorted Array

 

nums배열은 원래 오름차순이었지만 특정 기준에 따라 rotate되어있는 상태이다

 

기본적인 binary search 로직에 조건을 하나 더 추가한 것 뿐이다.

sort가 일부 rotate 되어 있으므로, left와 middle의 값을 비교하여 오름차순인지 내림차순이지만 보는 것이다

그리고 각 경우에 대해 로직을 반대로만 짜주면 된다.

사실 이 문제는 indexOf 메소드를 이용해 한 줄로 처리할 수도 있지만, 굳이 binary search를 적용한다면 이렇다.

 

 

예시2. 34 Find First and Last Position of Element in Sorted Array

 

조금 꼬인 예시를 보자. 

이번에는 target이 여러개 주어지고, 해당 타겟이 위치한 범위를 리턴하는 문제이다.

기존 bianry search는 left, right, target이 같아지는 순간까지 Loop를 돌렸으나, 해당문제는 범위를 구하는 문제이므로 설정을 달리 해줘야 한다.

 

기존에는 middle= target을 만족하면 리턴했다

그러나 target이 범위인 경우, middle이 target을 만족한다고 하여도 그 주위의 원소들도 target과 같은 값을 가질것이다.

 

이런 경우에는 start target과 end target을 별개로 구한다

위의 예시처럼 target이 middle을 만족하는 경우, 계속 앞으로 끌어당겨 루프를 돌려준다

 

결과적으로 target을 찾든, 찾지 않든간에 target이 nums[middle]의 값보다 클때만 left를 옮겨주고, 나머지는 right를 앞으로 끌어오면 된다

 

endTarget은 올림으로 찾아낸다. 이것 역시 targe이 middle보다 더 작은 값일때만 right를 옮겨주고 나머지 경우는 무조건 left를 늘려주는 것으로 한다.

 

start target은 target을 찾아도 무조건 left를 앞으로, end target은 right를 뒤로 하는 로직을 짜주면 된다.

 

 

 

예시3. 278. First Bad Version

 

예시2와 유사하지만 이번에는 element가 true or false로 구성되어 있다

 

원리는 똑같다.

이 경우도 [ F, F, F, F, .... T, T, T ] 같은 형태로 같은 숫자가 연달아 놓여있기 때문에, 특정 범위를 찾되 가장 앞의 인덱스를 찾는 문제와 동일하다

따라서 특정 인덱스를 찾으면 계속해서 범위를 앞쪽으로 줄여준다

 

 

예시4. 35. Search Insert Position

 

기본문제 간단히 하나만 더 풀어보겠다 

 

설명은 생략

 

 

예시5 . 300 Longest Increasing Subsequence

 

이번 문제는 nums에 대해 오름차순으로 증가하는 원소들만 모은 부분배열의 길이를 구하는 것이다.

복잡해보일수 있지만 dp나 binary search를 이용해 풀 수 있다

 

일단 복습겸 dp를 이용해 풀어보자

 

dp[ i ]는 i가 포함되는 최대 LIS이다.

이 원소가 업데이트 되는 조건은 비교군 j에서 i로 진행할 때 값이 증가하는 경우다.

하지만 이렇게 작성한 로직은 성능상의 문제를 갖게 된다.

 

우선 bs 함수를 만든다.

해당함수는 target을 찾아도 middle+1을 처리해준다. 즉, end target을 찾겠다는 뜻이다

 

이후 각 원소에 대해 bs를 수행해주는데, 이때 bs는 해당 원소보다 작은 위치를 찾아서 순서를 맞춰준다
오름차순으로 정렬된 memo원소에 대해 마지막 원소보다 target의 인덱스가 작다면 알아서 오름차순으로 맞추도록 대체될 것이기 때문이다.

이를 LIS라는데,자세한 풀이는 해당 문제 포스팅을 참고.

 

 

예시6. 334. Increasing Triplet Subsequence

 

거의 유사한 문제다

예시5와 같은 조건에 triplet임만 확인되면 true를 리턴하라는 문제

 

 

예시7. 240. Search a 2D Matrix II

 

마지막으로 2차원 행렬에서 binary search까지 알아보자

조건은 행렬이 각각 오름차순으로 정리되어있어야 한다는 것이다.

 

순회의 시작을 i=0, j=최대 부터 하면 된다

만약 target이 그보다 작다면 j를 내리고, target이 더 크다면 i를 높이며 찾는다