이진 검색 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

이진 검색 알고리즘(binary search algorithm)은 정렬된 리스트에서 특정한 값을 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값을 찾고자 하는 값과 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 된다. 이진 검색은 분할 정복 알고리즘의 한 예이다.


의사 코드[편집]

재귀같이 표현[편집]

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
}

high와 low를 지정[편집]

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