이진 탐색 (Binary Search)

 

wargame 풀다가, 이진 탐색을 이용한 문제라서,
간단하게 이진 탐색 코드를 짜보았습니다.

---

1. 이진탐색이란?

(1) 정의

- 오름차순으로 정렬된 리스트에서 특정 위치를 찾는 알고리즘이다.
- 비교 한 번할 때마다, 탐색 범위가 50%로 줄어든다.

 

(2) 과정

① 배열의 중간 값을 선택하여 찾고자하는 값과 비교한다.
② 찾고자 하는 값이 중간 값보다 크면 오른쪽을 대상으로, 작으면 왼쪽을 대상으로 정하여 탐색한다.
③ 이는 값을 찾을 때까지 탐색하는 것을 반복한다.

2. Code

- 해당 코드는 9가 존재하는 인덱스 위치를 알아내는 코드로 작성되었다.

#include <stdio.h>
#include <stdbool.h>

int main(){
	printf("\n   =====================\n");
	printf("      Binary Search!\n");
	printf("   =====================\n\n");
	
	int num[] = {1,2,3,4,5,6,7,8,9,10};
	int key = 9;
	int start = 0;
	int end = (sizeof(num)/sizeof(int))-start;
	int mid = 0;

	while(true){
		mid = (start+end)/2;
		printf("     Now mid : %d\n", mid);

		if(num[mid]<key){
			start = mid;
		}else if(num[mid]>key){
			end = mid;
		}else if(num[mid] == key){
			printf("\n   --------------------\n\n");
			printf("     Find %d index : %d\n\n",num[mid],mid);
			return 0;
		}else{
			printf("Error\n");
		}

	}

	return 0;
}

 

3. 결과

 

---

잘못되거나 부족한 부분이 있다면 댓글 남겨주세요~!
피드백은 언제나 환영입니다~~( •̀ ω •́ )✧