이진 검색 (Binary Search)

이진 검색이란?

- 이진 검색은 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘

- 배열의 중앙값을 기준으로 탐색 범위를 반으로 나누며, 찾고자 하는 값이 어느 쪽에 있는지에 따라 탐색 범위를 줄여 나감

- 탐색 범위가 절반으로 줄어들기 때문에 시간 복잡도가 O(log N)로 매우 효율적!

 

이진 검색 동작 원리

1. 중앙값을 찾기: 배열의 중앙 값을 찾는다
2. 비교: 찾고자 하는 값이 중앙값보다 작은지 큰지 비교
   • 작으면 왼쪽 절반을 다시 검색.
   • 크면 오른쪽 절반을 다시 검색.
3. 반복: 값을 찾을 때까지, 또는 검색 범위가 없어질 때까지 이 과정을 반복

---

이진 검색의 특성

• 정렬된 배열에서만 사용할 수 있다 (사용 전 필히 정렬하자)
• 값을 찾으면 그 인덱스를 반환하고, 값을 찾을 수 없으면 음수를 반환
• Arrays.binarySearch() 메서드는 내장 메서드로 제공되어 쉽게 활용 가능

---

Java 이진 검색 구현

1. 기본 이진 검색 알고리즘

public class BinarySearchExample {

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 중앙값 인덱스

            if (arr[mid] == target) {
                return mid;  // 값을 찾으면 인덱스 반환
            }
            if (arr[mid] < target) {
                left = mid + 1;  // 오른쪽 절반 탐색
            } else {
                right = mid - 1;  // 왼쪽 절반 탐색
            }
        }
        return -1;  // 값이 없으면 -1 반환
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        
        int result = binarySearch(arr, target);
        System.out.println(result);  // 출력: 3 (7은 arr[3]에 있음)
    }
}

---

2. Arrays.binarySearch() 내장 메서드 사용

import java.util.Arrays;

public class BinarySearchExample {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        
        // 내장 메서드 사용
        int result = Arrays.binarySearch(arr, target);
        System.out.println(result);  // 출력: 3 (7은 arr[3]에 있음)

        // 값이 없을 때
        int notFound = Arrays.binarySearch(arr, 4);
        System.out.println(notFound);  // 출력: -3 (4는 배열에 없으므로 삽입 위치는 2)
    }
}

• Arrays.binarySearch():
  • 반환값은 찾은 인덱스
  • 값을 찾지 못한 경우, 음수 값을 반환하는데 이는 (삽입 위치 + 1)이다.

---

이진 검색의 시간 복잡도

• 시간 복잡도: O(log N)
  • 매번 탐색 범위가 절반으로 줄어들기 때문에, 매우 효율적

---

이진 검색의 사용 예시

• 정렬된 배열에서 특정 값의 위치 찾기
• 주어진 값의 존재 여부 확인
• 이진 탐색 트리에서 값 검색

---

주의 사항

1. 배열이 반드시 정렬되어 있어야 이진 검색을 사용할 수 있다 *********************  (Arrays.sort() 사용하자)
2. 값이 없을 경우 음수로 반환되므로, 이 값을 활용한 처리도 필요

 

내장메서드는 정말 꿀인듯 ?!?!,,,  잘 사용하도록 하자