<알고리즘>이진탐색(BST)

자료구조에서 이진탐색을 설명했으므로 여기선 간략하게 정리하겠다.

	public static int binarySearch(int arr[], int target) {
        //인덱스 지정
        int left = 0; 
        int right = arr.length - 1;

        while (left <= right) { // left, right가 만날 때까지
            int mid = (left + right) / 2;

            if (target == arr[mid]) {   // 해당 데이터 찾음
                return mid;
            } else if (target < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 해당 데이터 없는 경우
        return -1;
    }

int mid = (left + right) / 2;
만약 오버플로우가 된다면
int mid = left + (right - left) / 2; 로 하면 된다.

재귀적으로 구현

인자를 int[] arr, int target, int left, int right를 받아서 재귀적으로 탐색한다.

public static int binarySearch2(int[] arr, int target, int left, int right) {
        if (left > right) { // 해당 데이터 없는 경우
            return -1;
        }

        int mid = (left + right) / 2;

        if (target == arr[mid]) {  // 해당 데이터 찾음
            return mid;
        } else if (target < arr[mid]) { 
            return binarySearch2(arr, target, left, mid - 1); //right인자를 mid-1로
        } else {
            return binarySearch2(arr, target, mid + 1, right);//left인자를 mid+1로
        }
    }