이진 탐색

 

 

알고리즘

 

정렬된 배열에서
특정 값을 찾습니다.

 

 

What ?

이진탐색

분할 정복(divide and conquer) 방식으로 동작해 배열이 정렬되어 있어야 합니다.

시간 복잡도는 "O(log n)"입니다.

---

How ?

이진탐색

 

배열의 중간 원소를 선택합니다.

↓

찾는 값이 중간 원소보다 작으면 배열의 왼쪽 절반을 탐색합니다.

↓

찾는 값이 중간 원소보다 크면 배열의 오른쪽 절반을 탐색합니다.

↓

위 과정을 반복해 값을 찾고, 배열의 범위가 더 이상 유효하지 않으면 종료합니다.

 

 

Example

❓  [1, 3, 5, 7, 9, 11, 13, 15, 17]이란 배열에서, 값 5를 찾아야 합니다.

low = 0, high = 8 (배열의 시작과 끝 인덱스)
중간 값은 (0 + 8) / 2 = 4 (인덱스 4의 값: 9)
5 < 9이므로, high = 3으로 설정하여 왼쪽 절반을 탐색합니다.
low = 0, high = 3
중간 값은 (0 + 3) / 2 = 1 (인덱스 1의 값: 3)
5 > 3이므로, low = 2로 설정하여 오른쪽 절반을 탐색합니다.
low = 2, high = 3
중간 값은 (2 + 3) / 2 = 2 (인덱스 2의 값: 5)
5 == 5이므로 값을 찾았음을 확인하고, 2를 반환합니다.

 

// 코드
public class BinarySearch {
    
    // 이진 탐색 알고리즘: 반복문을 사용
    public static int binarySearch(int[] arr, int target) {
        int low = 0;                   // 배열의 시작 인덱스
        int high = arr.length - 1;      // 배열의 끝 인덱스
        
        while (low <= high) {
            // 중간 인덱스를 계산
            int mid = (low + high) / 2; 
            // 목표 값이 중간 값과 일치하는지 확인
            if (arr[mid] == target) {
                return mid;  // 찾은 값의 인덱스를 반환
            }
            // 목표 값이 중간 값보다 작으면, 오른쪽 절반을 제외
            else if (arr[mid] > target) {
                high = mid - 1;
            }
            // 목표 값이 중간 값보다 크면, 왼쪽 절반을 제외
            else {
                low = mid + 1;
            }
        }
        return -1;  // 목표 값이 배열에 없으면 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17};  // 정렬된 배열
        int target = 5;  // 찾고자 하는 값
        int result = binarySearch(arr, target);  // 이진 탐색 수행
        if (result == -1) {
            System.out.println("값을 찾을 수 없습니다.");
        } else {
            System.out.println("값을 찾았습니다. 인덱스: " + result);
        }
    }
}

---

Feature !

이진탐색

정렬된 배열에서만 가능: 이진 탐색은 배열이 정렬되어 있을 때만 동작합니다. 정렬되지 않은 배열에서는 이진 탐색을 사용할 수 없습니다.

효율적: 일반적인 선형 탐색(O(n))에 비해 매우 효율적입니다. 특히 데이터가 많을수록 성능 차이가 크게 나타납니다.

반복문과 재귀를 이용한 구현: 이진 탐색은 반복문(iterative) 또는 재귀(recursive)를 이용해 구현할 수 있습니다.

각 단계에서 탐색 범위를 절반씩 줄여가기 때문에 시간 복잡도는 **O(log n)**입니다.

---

분야	설명
정렬 리스트에서 값 찾기	정렬된 배열에서 특정 값을 빠르게 찾을 때 사용됩니다.
범위 탐색	주어진 시간 내에 최대한 처리할 수 있는 작업의 수를 찾아야 하는 경우 사용됩니다.
이진 탐색 트리	이진 탐색의 원리를 확장한 자료구조로, 데이터를 빠르게 삽입, 삭제, 검색하는 데 사용됩니다.
데이터베이스 인덱싱	데이터베이스에서 정렬된 데이터에 대해 빠르게 검색할 때 이진 탐색이 사용될 수 있습니다.

---