이진 탐색(binary search)

개념

---

오름차순으로 정렬된 리스트에서 특정한 값을 찾는 알고리즘입니다

 

 

의사코드

---

BinarySearch(A[0..N-1], value, low, high) {
  if (high <= low)
    return -1 // not found
  mid = (low + high) / 2
  if (A[mid] > value)
    return BinarySearch(A, value, low, mid-1)
  else if (A[mid] < value)
    return BinarySearch(A, value, mid+1, high)
  else
    return mid // found
}

BinarySearch(정렬된 배열, 찾을 값, 배열의 첫 인덱스, 배열의 마지막 인덱스)

를 통해 이진 탐색을 수행할 수 있습니다

 

 

활용

---

그러면 해당 알고리즘을 코테 문제에 어떻게 적용할 수 있는지 생각해 보겠습니다.

 

https://www.acmicpc.net/problem/1300

https://www.acmicpc.net/problem/1939

 

제가 푼 위의 문제들 같은 경우 정렬된 숫자 배열을 탐색하는 것처럼

답의 범위가 정해져 있고

특정 답을 확인한 후 답이 될 수 있는 범위를 좁혀 나갈 수 있어

이진 탐색을 적용할 수 있습니다.

 

즉, 답의 전체 범위를 배열로 잡고 이진탐색을 통해 답을 빠르게 찾을 수 있습니다.

 

 

Reference

---

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98