[알고리즘] 이진 탐색

정의

이진 탐색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의로 선택해, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

의사 코드

// 재귀
이진탐색(arr, target, low, high) {
    if high <= low { // 관계 역전 -> 값 존재 X
        return -1
    }
    mid = (low + high) / 2 // 중간 값 선언
    // 배열에 대해 이진탐색 실행
    if arr[mid] > target { 
        return 이진탐색(arr, target, low, mid - 1)
    } else if arr[mid] < target {
        return 이진탐색(arr, target, mid + 1, high)
    } else {
        return mid;
    }
}

이진탐색(arr, target) {
    low, high = 0, arr.length - 1;
    while (low <= high) {
        mid = (low + high) / 2;
        if arr[mid] > value {
            high = mid - 1
        } else if arr[mid] < value {
            low = mid + 1
        } else {
            return mid
        }
    }
    return -1
}

• 중간 값이 target보다 크면 반으로 나눈 배열 중 왼쪽 배열에 target이 존재할 수 있다. high가 mid - 1로 바뀌고 다시 이진탐색 실행
• 중간 값이 target보다 작으면 반으로 나눈 배열 중 오른쪽 배열에 target이 존재할 수 있다. low가 mid + 1로 바뀌고 다시 이진탐색 실행