[알고리즘] 이진 탐색이란?

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 알고리즘입니다.

이진 탐색은 반복문(Iterative)을 이용한 구현과 재귀(Recursive)를 이용한 구현이 가능합니다.

이진 탐색 알고리즘의 시간 복잡도는 O(log n)입니다.

아래는 이진 탐색 알고리즘을 Java로 구현한 예시입니다.

public static int binarySearch(int[] array, int target) {
    int left = 0;           // 배열의 가장 왼쪽 인덱스
    int right = array.length - 1;   // 배열의 가장 오른쪽 인덱스
    
    while (left <= right) {
        int middle = (left + right) / 2;    // 중간 인덱스 계산
        
        if (array[middle] == target) {
            // 찾는 값과 중간 값이 같으면, 해당 인덱스를 반환합니다.
            return middle;
        } else if (array[middle] < target) {
            // 중간 값이 찾는 값보다 작으면, 오른쪽 반 배열을 탐색합니다.
            left = middle + 1;
        } else {
            // 중간 값이 찾는 값보다 크면, 왼쪽 반 배열을 탐색합니다.
            right = middle - 1;
        }
    }
    // 배열에서 찾는 값이 없는 경우, -1을 반환합니다.
    return -1;
}

 

위 코드에서 left는 배열의 가장 왼쪽 인덱스를, right는 배열의 가장 오른쪽 인덱스를 나타냅니다.

while 문 안에서는 배열의 중간 인덱스를 계산하여, 찾는 값과 비교합니다.

만약 중간 값과 찾는 값이 같으면, 중간 인덱스를 반환합니다.

그렇지 않으면, 찾는 값이 중간 값보다 작으면, 배열의 오른쪽 반 배열을 탐색하고, 찾는 값이 중간 값보다 크면, 배열의 왼쪽 반 배열을 탐색합니다.

이를 반복하여, 찾는 값이 없거나, 찾는 값의 인덱스를 찾을 때까지 탐색합니다.