[자료구조] 이진탐색

#include <stdio.h>

int search(int a[], int len, int target){
int first = 0;
int last = len - 1; // 왜 len이 아니라 len-1일까?
int mid;

while (first <= last){ // 왜 last가 크거나 같아야하는가?

mid = (first + last) / 2;
if (a[mid] == target){
return mid;
}
else {
if (a[mid] > target){
last = mid - 1; // mid에 -1이 없다면 찾는 값이 1일때 무한 반복한다.
}
else{
first = mid + 1; // mid에 +1이 없다면 찾는 값이 5일때 무한 반복한다.
}
}
}
return -1;
}

int main(){
int a[] = { 0, 1, 2, 3, 4 };
int result;
result = search(a, sizeof(a) / sizeof(int), 4);

if (result == -1){
puts("탐색이 실패했습니다.");
}
else{
printf("탐색한 인덱스 %d \n", result);
}
return 0;
}

- 이진탐색은 인덱스가 미리 정렬되어 있어야 한다는 제한이 있다.
- mid값의 대소를 비교하여 first 또는 last를 제한한다는 것이 특징이다.
- last가 len-1인 이유는 01234가 있을때 가운데 값은 2다. (0+4)/2 = 2 (0+5)/2 = 2 더 정확한 값은 4/2다.
- first < last라면 4를 예로 들어도 아래 그림처럼 first와 last가 같아진다. 리턴하기전에 while문에서 나가면 안된다.

그림

target first last mid count
4 0 4 2 1
4 3 4 3 2
4 4 4 4 3 -> 리턴