이진 검색 알고리즘
위키백과 ― 우리 모두의 백과사전.
이진 검색 알고리즘은 정렬된 리스트에서 특정한 값을 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값을 찾고자 하는 값과 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 된다. 이진 검색은 분할 정복 알고리즘의 한 예이다.
[편집] 예제 알고리즘
이 예제는 재귀적으로 표현한 이진정렬이다.
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 }
다음은 low와 high를 미리 지정함으로써 가장 많이 쓰이는 예제이다.
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 j } return -1 // not found k }
 |
이 문서는 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |
