이분 탐색 (Binary Search)

1. 개요

• 정렬된 배열에서 특정 요소의 위치를 찾기 위한 알고리즘이다.
• 탐색 범위를 반으로 줄여가며 원하는 값을 찾는다.
• 배열이 정렬되어 있을 때만 사용할 수 있으며, 매우 빠른 탐색 속도를 가진다.

---

2. 특징

• 시간 복잡도: O(log n)
• n은 배열의 크기
• 탐색 범위를 매 단계마다 반으로 줄임으로써, 대규모 데이터셋에서도 빠른 탐색을 가능하게 한다.

---

3. 코드

public class BinarySearchTest {

	public static void main(String[] args) {
		int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16 };
		int target = 10;

		int resultIndex = binarySearch(arr, target);

		if (resultIndex != -1) {
			System.out.println(resultIndex);
		} else {
			System.out.println("No Element");
		}
	}

	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;
			}
			// 중간값이 타겟값보다 큰 경우, 오른쪽 탐색 범위를 줄임
			else if (arr[mid] > target) {
				right = mid - 1;
			}
			// 중간값이 타겟값보다 작은 경우, 왼쪽 탐색 범위를 줄임
			else {
				left = mid + 1;
			}
		}

		// 타겟값을 찾지 못한 경우
		return -1;
	}

}