C언어 : 이진 탐색 (binary search)
글 작성자: _rian
Binary Search
이진탐색이란?
데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비교한다. x가 중간값보다 작으면 중간 값을 기준으로 좌측의 데이터들을, x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.
- 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인
- 이진 탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
예시
이미 정렬되어있는 10개의 데이터 중에서 4인 원소를 찾는다고 해보자.
이진 탐색의 시간 복잡도
- 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 O(log2N)�(log2�)
- 탐색 범위를 절반씩 줄여나가므로 시간 복잡도는 O(\logN)�(\logN)을 보장한다.
이진탐색은 오름차순으로 정렬된 정수배열에서 원하는 정수를 찾는 데에 유용하다.
아래 코드는 탐색이 성공하면 해당 인덱스를 반환하고 실패하면 -1을 반환하는 코드이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// data : 탐색할 오름차순으로 정렬된 정수 배열
// n : 정수 배열의 크기
// key : 찾고자하는 값
int binsearch(int data[], int n, int key) {
int low, high;
int mid;
low = 0;
high = n - 1;
while (low <= high) {
mid = (low + high) / 2;
if (key == data[mid]) { //탐색 성공
return mid;
}
else if (key < data[mid]) { //탐색 범위를 아래쪽으로
high = mid - 1;
}
else if (key > data[mid]) { //탐색 범위를 위쪽으로
low = mid + 1;
}
}
return -1; //탐색 실패
}
|
cs |
메인 함수와 함께 사용한 것은 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <stdio.h>
int binsearch(int data[], int n, int key);
int main(int argc, char *argv[])
{
int a[10] = { 2, 8, 13, 16, 20, 22, 34, 45, 56, 77 }; //정렬된 자료
int index;
int key;
scanf("%d", &key);
index = binsearch(a, 10, key);
if (index == -1) {
printf("자료가 없습니다!\n");
}
else {
printf("자료가 %d번째에 있습니다.\n", index + 1);
}
return 0;
}
|
cs |
'Computer Engineering > C' 카테고리의 다른 글
C언어 : 특정 단어가 입력될 때 까지 단어를 입력받기 (0) | 2018.12.15 |
---|---|
문자열 처리 함수 strlen과 strcpy 만들기 (0) | 2018.12.15 |
C언어 : 스택(stack) , 배열을 사용해 스택 구현하기 (0) | 2018.12.15 |
C언어 : 기존 버블정렬과 개선된 버블 정렬 (bubble sort) (0) | 2018.12.15 |
C언어 콘솔창 텍스트 색상 지정 (0) | 2018.11.18 |
댓글
이 글 공유하기
다른 글
-
문자열 처리 함수 strlen과 strcpy 만들기
문자열 처리 함수 strlen과 strcpy 만들기
2018.12.15 -
C언어 : 스택(stack) , 배열을 사용해 스택 구현하기
C언어 : 스택(stack) , 배열을 사용해 스택 구현하기
2018.12.15 -
C언어 : 기존 버블정렬과 개선된 버블 정렬 (bubble sort)
C언어 : 기존 버블정렬과 개선된 버블 정렬 (bubble sort)
2018.12.15 -
C언어 콘솔창 텍스트 색상 지정
C언어 콘솔창 텍스트 색상 지정
2018.11.18