[C++] 이분 탐색

이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다.

이러한 이분 탐색은 실생활에서도 많이 쓰인다.

 

최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다.

1~100 까지의 수라고 하면, 50을 물어보고 up down을 해서 범위를 좁혀나가는게 가장 현명하다.

이 방법이 이분 탐색이다.

 

C++에서는 #include<iostream>을 통해 binary_search라는 함수를 사용할 수 있다.

이 경우 원하는 요소가 있으면 1을 반환, 없으면 0을 반환한다.

그런데 보통의 알고리즘 문제에서는 1, 0을 반환하는 것 뿐만 아니라 해당 요소의 인덱스 (위치) 등을 물어볼 수도 있기 때문에 이를 구현할 줄 알아야한다.

---

함수를 이용해서 풀 수도 있다.

주의해야할 점은, 이분 탐색에서는 정렬이 필수라는 점이다.

위에서 게임을 예시로 들었듯이, 50에서 up 이면 50 위 배열에서 찾아야하는데 정렬이 안되어 있으면 어디가 50이라는 숫자의 윗 부분인지 알 수가 없기 때문이다.

---

이를 구현하기 위해서는 left와 right를 설정해야한다. left는 배열의 맨 앞부분이고, right는 배열의 맨 뒷부분이다. 그리고 중간값 mid를 설정한다.

 

• 배열[mid] 값이 (= arr[mid] ) 찾고자 하는 값인지 확인한다. 찾고자 하는 값이면 true를 리턴한다.
• 찾고자 하는 값이 배열[mid] 값 보다 작으면 right = mid - 1 를 해준다. mid는 찾고자 하는 값이 아니므로 빼고, 그 바로 아래의 값을 상한선으로 잡아 그 안에서 탐색하면 된다. (50을 불렀을 때 up이라고 한다면 51~100사이라고 유추하는 것과 같다)
• 찾고자 하는 값이 배열[mid] 값 보다 크면 left = mid + 1을 해주면 된다. (50을 불렀을 때 down이라고 한다면 1~49 사이라고 유추하는 것과 같다.)

그러다가 left>right 가 되는 지점에서 탐색을 멈춘다. 이때까지도 탐색이 안된다면 그 수는 배열에 존재하지 않는 것이다!

 

---

 

upperBound 와 lowerBound 에 대해 알아야한다.

[ 1 2 2 2 3 ] 라는 배열이 있다고 했을 때, 2를 찾는다고 가정해보자.

lowerBound는 내가 찾는 카드의 가장 작은 인덱스 (여기서는 1) 를 의미하고

upperBound는 내가 찾는 카드의 가장 큰 인덱스 + 1을 한 값을 의미한다. (여기서는 4)

그리고 upperBound - lowerBound를 해준다 그러면 3이라는 값이 나오는데, 이 값이 같은 숫자 카드들의 갯수이다.

---

upperBound와 lowerBound를 구해보자.

 

우선 lowerBound는 가장 작은 인덱스를 구하면 된다.

그러므로 만약 내가 찾고자 하는 숫자가 mid 위치와 같거나 작으면 right를 옮겨준다.

1. (찾고자 하는 값이) mid와 같을 경우 = 더 왼쪽에 같은 숫자가 있으면 왼쪽으로 가야한다.

그러므로 현재 mid값 보다 하나 작은 위치로 right를 이동한다. 그러므로 right = mid - 1; 을 한 것이다.

근데 이동했는데 다른 숫자가 있으면? mid -1 한 값에 다른 숫자가 있는 것이고, mid 값에는 찾는 숫자가 있는 것이니 mid 값이 lowerBound 이다.

즉 mid 값인 right + 1을 리턴해주자!!

2. (찾고자 하는 값이) mid 보다 작은 경우 = 1~100 중 50을 불렀는데 down이라고 한 상황이 된 것이다. 그러면 1~49를 탐색해야한다. 그러므로 right = mid - 1; 을 한 것이다.

+ (찾고자 하는 값이) mid 보다 큰 경우 = 1~100 중 50을 불렀는데 up이라고 한 상황이 된 것이다. 그러면 51~100을 탐색해야한다. 그러므로 left = mid + 1; 을 한 것이다.

---

upperBound도 비슷하다. 찾고자 하는 값이 mid보다 작으면 right를 mid보다 작은 값으로 옮겨주면 된다.

그런데 mid와 같거나 mid보다 크면 생각을 해봐야한다.

1. (찾고자 하는 값이) mid와 같을 때 = 해당 mid 오른쪽에 같은 수가 더 있나? 생각해봐야한다.

2. (찾고자 하는 값이) mid보다 클 때 = left를 mid 다음 값으로 넘겨주자.

여기서는  왜 리턴 right + 1을 할까?

현재 right값은 해당 수의 가장 뒷 번호 index를 가리키게 된다.

upperBound는 그 index + 1 값이니 right +1를 한 것이다.

left가 right를 벗어나는 순간 while이 종료되므로 right + 1 은 곧 left와도 같다. return left 해도 된다.

 

말로 하려니 복잡하지만 그림을 그려보거나 관련 애니메이션을 보면 바로 이해가 될 수도 있다!

추가적으로... 이분 탐색은 정렬이 되어있어야만 가능하다. 꼭 정렬을 하자!! (2번이나 까먹음)

 

 

 

 

 

[C++] 백준 알고리즘 1920 수 찾기 (이분 탐색) (tistory.com)

[C++] 백준 알고리즘 1920 수 찾기 (이분 탐색)

[C++] 백준 알고리즘 10816 숫자 카드 2 (이분 탐색) (tistory.com)

[C++] 백준 알고리즘 10816 숫자 카드 2 (이분 탐색)