이진검색 설명:
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
이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여,
ko.wikipedia.org
구현 예제
#include <stdio.h>
#include <assert.h>
/*
* high must be length of arr -1
* /
int binary_search(int value, int low, int high, int* arr) {
while (low <= high) {
int mid = (low+high)/2;
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
low = mid+1;
} else {
high = mid-1;
}
}
return -1;
}
/*
* high must be length of arr -1
* /
int binary_search_recursive(int value, int low, int high, int *arr) {
if (low > high) return -1;
int mid = (low + high) / 2;
if (arr[mid] == value) {
return mid;
} else if (arr[mid] < value) {
return binary_search_recursive(value, mid+1, high, arr);
} else {
return binary_search_recursive(value, low, mid-1, arr);
}
}
void test() {
int number[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
int arr_size = (int) sizeof(number)/sizeof(int);
assert(binary_search(11, 0, arr_size-1, number) == 11);
assert(binary_search(2, 0, arr_size-1, number) == 2);
assert(binary_search(12, 0, arr_size-1, number) == -1);
assert(binary_search_recursive(11, 0, arr_size-1, number) == 11);
assert(binary_search_recursive(2, 0, arr_size-1, number) == 2);
assert(binary_search_recursive(12, 0, arr_size-1, number) == -1);
}
int main(int argc, char **argv) {
test();
return 0;
}
'Coding > CPP 삽질기' 카테고리의 다른 글
| Stack과 Heap (0) | 2021.02.25 |
|---|---|
| [C] Binary search (0) | 2020.12.06 |
| Quick sort (0) | 2017.07.13 |
| Bit 연산 정리 (0) | 2016.08.20 |
댓글을 달아 주세요