[알고리즘] 이진탐색(Binary Search) -C/C++

<이진탐색(Binary Search)> 

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식이다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

 

• 장점 : 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다
• 단점 : 정렬된 리스트에만 사용할 수 있다
• 시간복잡도 : O(logN)

<Binary Search>

int binarySearch(int arr[], int searchData, int start, int end){
	if (start > end)	return -1;

	int mid = (start + end) / 2;

	if (arr[mid] == searchData)	
		return mid;
	else if (arr[mid] > searchData)
		binarySearch(arr, searchData, start, mid - 1);
	else
		binarySearch(arr, searchData, mid + 1, end);
}

<main>

#define SIZE 9

int main() {
	int arr[SIZE] = { 1, 2, 5, 7, 9, 12, 21, 23, 27 };
	int search_idx = binarySearch(arr, 12, 0, SIZE - 1);

	if (search_idx >= 0)	printf("search : %d\n", search_idx);
	else		printf("No data\n");
}

 

 

참고사이트 : 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