이진 탐색 알고리즘 (Binary Search)

이전 글에서 다룬 순차 탐색 알고리즘보다 훨씬 좋은 성능을 보이는 알고리즘입니다. 

순차 탐색 알고리즘은 O(n), 이진 탐색 알고리즘은 O(logN)의 시간복잡도를 나타냅니다.

첫번째 index를 first라 하고 마지막 index를 last라 하여 범위를 반으로 좁혀가면서 탐색합니다. 

선행조건 - 배열에 저장된 데이터들은 정렬되어 있어야 합니다.
while문의 조건 - first <= last 


#include <stdio.h> int B_Search(int arr[], int length, int target) { int first = 0, last = length-1; int midIndex; while(first<=last) // first가 last보다 커질 때 loop 탈출 { midIndex = (first + last)/2; if(arr[midIndex] == target) return midIndex; else { if(arr[midIndex] < target) first = midIndex + 1; else last = midIndex - 1; } } return -1; } int main() { int arr[] = {1, 3, 5, 7, 9}; int idx; int target; scanf("%d", &target); idx = B_Search(arr, sizeof(arr)/sizeof(int), target); if(idx == -1) printf("탐색 실패\n"); else printf("%d의 index값은 %d이다\n", target, idx); return 0; }

[출처] 윤성우의 열혈 자료구조 - Orange Media