[Java] 이진 탐색(Binary Search)

🔎이진 탐색 (Binary Search)

이진 탐색 또는 이분 탐색이라고 불리는 이 탐색법은, 정렬된 배열에서 특정 값을 찾는 알고리즘을 의미한다.

🛠️작동 과정

이진 탐색은 배열의 중간 요소를 확인하여 찾고자 하는 값이 중간 요소보다 큰 지 작은 지 판단한다.
찾고자 하는 값이 중간 요소보다 작으면, 중간 요소 왼쪽의 절반을 탐색하고,
찾고자 하는 값이 중간 요소보다 크면, 중간 요소 오른쪽의 절반을 탐색한다.

이진 탐색은 탐색 범위를 절반 씩 줄여 나가기 때문에, 선형 탐색(Linear Search)에 비해 빠른 속도를 보장한다.
하지만, 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에, 배열이 정렬되어 있지 않은 경우에는 정렬 작업이 필요하다.

자세한 작동 과정은 아래와 같다

1. 배열의 가운데 요소를 확인한다.
2. 가운데 요소가 원하는 값과 일치하면 해당 요소의 인덱스를 반환한다.
3. 가운데 요소가 원하는 값보다 크면, 배열의 왼쪽 절반에서 탐색을 계속한다.
4. 가운데 요소가 원하는 값보다 작으면, 배열의 오른쪽 절반에서 탐색을 계속한다.
5. 원하는 값을 찾을 때까지 1~4단계를 반복한다.
6. 검색 범위가 더 이상 없을 때까지 원하는 값을 찾지 못한 경우, 값이 배열에 없다고 판단하여 -1 또는 적절한 오류 코드를 반환한다.

---

⭐특징

효율적인 탐색 시간

배열의 길이를 n이라고 했을 때, 이진 탐색의 시간 복잡도는 $O(log n)$이다.
이진 탐색은 정렬된 배열에서 빠르게 값을 찾을 수 있기 때문에, 입력 배열이 크더라도 효율적인 시간을 보여준다.

적은 비교 횟수

이진 탐색은 매 반복마다 배열을 반으로 나누어 탐색하기 때문에, 선형 탐색에 비해 적은 비교 횟수로 원하는 값을 찾을 수 있다.

🚨주의점

정렬된 배열에서만 사용 가능

앞서 언급했듯이, 이진 탐색은 정렬된 배열에서만 사용할 수 있다.
정렬되지 않은 배열에서 이진 탐색을 사용하려면 먼저 정렬을 해야 하는데,
이 때, 정렬에 소요되는 시간이 추가적으로 필요하므로, 탐색 전에 정렬을 수행해야 하는 경우 이진 탐색의 효율성이 상대적으로 감소할 수도 있다.

임의 접근이 가능한 데이터 구조에서만 사용 가능

이진 탐색은 배열과 같이 임의 접근이 가능한 데이터 구조에서만 사용할 수 있다.
즉, 연결 리스트와 같은 순차 접근 데이터 구조에서는 이진 탐색을 사용하려면 비효율적일 수 있다.

데이터의 중복성 처리

이진 탐색은 중복된 값을 가진 배열에서 특정 값의 첫 번째 또는 마지막 인덱스를 찾는 데 추가적인 처리가 필요하다.
이 경우에는, 처음부터 끝까지 배열을 탐색해 중복된 값의 첫 번째 인덱스를 찾아내는 선형 탐색이 더 적합할 수 있다.

---

👾구현 예제

public 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;
        }
        else if (arr[mid] < target) {
        	left = mid + 1;
        }
        else {
        	right = mid - 1;
        }
    }
    return -1;
}

🔎관련 문제