이진탐색

목적과 특징

💡 조사범위를 절반씩 줄여가며 원하는 원소를 찾는 전략

• 두개의 포인터(left, right)를 활용해 조사범위를 설정한다
• 찾고자하는 원소와 middle 값의 크기를 비교해서 조사범위를 조정한다
  • middle 값이 찾고자하는 원소보다 큰 경우, 왼쪽 조사를 위해 right의 인덱스를 내려서 갱신
  • middle 값이 찾고자하는 원소보다 작은 경우, 오른쪽 조사를 위해 left의 인덱스를 올려서 갱신
• 찾고하는 값이 있는 경우에 해당 원소의 인덱스를, 없으면 -1을 반환한다.

구현코드

C++

int BinarySearch(int *arr, int n, int x) // 이진 탐색
{
    int left = 0;
    int right = n - 1;

    while (left <= right) {

        int middle = (left + right) / 2; // 정수 나누기 (버림)

        if (arr[middle]> x) { // REVIEW: 찾고자하는 값과 지금 값 구분
            right = middle - 1;
        } else if (arr[middle] < x) { // REVIEW: 찾고자하는 값과 지금 값 구분
            left = middle + 1;
        } else {
            return middle;
        }
    }

    return -1; // Not found
}

• x < arr[middle]: 조사범위를 왼쪽으로 조정하기 위해 right의 인덱스를 조정
• x > arr[middle]: 조사범위를 오른쪽으로 조정하기 위해 left의 인덱스를 조정