부분부분 나누어 살펴보자. linear_search 메서드처럼 binary_search도 array와 search_value를 인수로 받는다.

다음처럼 binary_search 메서드를 호출한다.

p binary_search([3, 17, 75, 80, 202], 22)

메서드는 가장 먼저 search_value가 있을 수 있는 인덱스 범위를 정한다. 다음처럼 하면 된다.

lower_bound = 0
upper_bound = array.length - 1

검색을 시작할 때는 search_value가 전체 배열 어디에든 있을 수 있으므로 lower_bound를 첫 번째 인덱스로, upper_bound를 마지막 인덱스로 정한다.

실제 검색은 while 루프 안에서 수행된다.

while lower_bound <= upper_bound do

이 루프는 search_value를 찾을 수 있는 원소가 남아 있을 때까지 수행된다. 곧 알아보겠지만 알고리즘은 이 범위를 계속해서 좁혀 간다. lower_bound <= upper_bound 절은 언젠가 범위가 남아 있지 않는 상황에 도달하고 이때 search_value가 배열에 없다고 판단할 수 있다.

루프 내 코드는 범위의 midpoint에 있는 값을 확인한다. 다음과 같이 수행한다.

midpoint = (upper_bound + lower_bound) / 2
value_at_midpoint = array[midpoint]