이원 탐색(binary search), 이진 탐색, 매크로

n ≥ 1개의 서로 다른 정수가 이미 정렬되어 배열 arr에 저장되어 있다고 가정하자. 정수 target이 배열 arr에 있는가를 검사하려고 한다.

만일 존재한다면 arr[i] = target인 인덱스 i를 반환하고, 그렇지 않다면 -1을 반환한다. 배열 arr이 정렬되어 있기 때문에 다음과 같은 방법을 사용할 수 있다. left, right는 탐색하고자 하는 배열의 왼쪽, 오른쪽 끝 지점을 가리킨다.

초기 값으로 left=0, right=n-1로 하고 중간 위치를 mid로 설정하여 arr[mid]와 target을 비교하여 다음과 같은 세 가지 경우 중 하나를 고려할 수 있다. 1) target < arr[mid] : 이 경우 target은 arr[0]과 arr[mid-1] 사이에 존재하므로 right을 mid-1로 설정한다. 2) target = arr[mid] : 이 경우는 mid를 반환한다. 3) target > arr[mid] : 이 경우 target은 arr[mid+1]과 ...