• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법임.
• 내부 데이터가 정렬되어 있어야만 사용 가능함.
• start, end, mid를 사용하여 탐색.
  • left, right로도 사용함.

알고리즘

• 중간 값을 임의의 값으로 선택함.
• 임의의 값과 찾고자 하는 값을 비교함.
• 비교 결과 임의의 값이 더 크다면 우측을 대상으로, 작다면 좌측을 대상으로 다시 탐색함.
• 위 과정을 반복.

예시

오름차순으로 정렬된 배열로 탐색 실행. → [17, 28, 43, 67, 88, 92, 100]

• 배열의 3번째 원소인 43을 찾는다고 가정.
• 가운데에 위치한 임의의 값 67 선택.
• 67과 43을 비교함. 67이 더 크기 때문에 찾고자하는 값은 좌측에 존재함.
• 좌측 배열로 다시 탐색 진행. → [17, 28, 43]
• 임의의 값 28 선택
• 28 < 43 이므로, 우측에 위치하는 것을 알 수 있음.
• 43 == 43 탐색 종료

소스코드 - Kotlin

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1

    while (left <= right) {
        val mid = (left + right) / 2

        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1  // 탐색 실패시 -1 반환
}

범위 및 함수 사용시 유의사항