ex) {1, 5, 7, 13, 15, 23}으로 정렬된 배열이 있을 때 15라는 값을 찾고자 하는 경우
1. 인덱스가 0 ~ 5인 정렬된 배열이므로 중간값은 (0 + 5) / 2 = 2, 인덱스가 2인 값이 중간값이 되며 해당 값은 7입니다. 따라서 7과 비교할 값 15를 비교했을 때 7이 더 작으므로 배열에서 해당 값 보다 큰 오른쪽에 나열된 13, 15, 23과 비교하게 됩니다.
int BinarySearch(int sortArr[], int target){
int min = 0; // // sortArr에서 최소 index값을 얻음
int max = sortArr.length -1; // sortArr에서 최대 index값을 얻음
int middle; // 정렬된 sortArr이라는 배열에서 중간 인덱스 값을 얻을 변수
// 최소 인덱스 값이 최대 인덱스 값보다 클 경우 중간 인덱스 값이 음수가 나오게 되므로 비교 불가
while(min <= max){
middle = (min + max) / 2;
if (sortArr[middle] == target){
return middle;
}else if(sortArr[middle] > target){ // 찾고자 하는 target 값보다 중간값이 큰 경우왼쪽 값들을 비교합니다.
max = middle - 1;
}else{
min = middle + 1;
}
return -1;
}
}
int BinarySearchRecursive(int sortArr[], int target, int min, int max){
// 재귀함수를 종료할 시점을 나타내줍니다. 위 반복문 방법에서 while 조건문과 비교하시면 이해하기가 좀 더 쉽습니다.
if(min > max){
return -1;
}
int middle = (min + max) / 2; // sortArr의 중간 인덱스 값을 구합니다.
// 찾고자 하는 값을 정렬된 배열에서 찾았다면 해당 인덱스를 반환해주고 재귀함수를 종료합니다.
if (sortArr[middle] == target){
return middle;
}else if(sortArr[middle] > target){
return BinarySearchRecursive(sortArr, target, min, max-1);
}else{
return BinarySearchRecursive(sortArr, target, mid+1, max);
}
}