[심화] 이진탐색 & 이진탐색트리

이진탐색

개념

탐색 알고리즘

1. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교
2. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색

구현

반복문 이용

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

재귀함수 이용

이진탐색트리