이분 탐색 Binary Search

Intro::

이분 탐색에 대해 알아보자.

정의

탐색 범위를 두 부분으로 분할하면서 찾는 방식이다. 이분 탐색을 하기 전에 정렬된 상태여야 한다.

1. 우선 정렬을 해야 함

2. left와 right로 mid 값 설정

3. mid와 내가 구하고자 하는 값과 비교

4. mid보다 높으면 : left = mid+1, mid보다 낮으면 : right = mid - 1

5. left > right가 될 때까지 계속 반복하기

시간 복잡도

• 전체 탐색 : O(N)

• 이분 탐색 : O(logN)

코드

package algorithm;

import java.util.Arrays;
import java.util.NoSuchElementException;

public class BinarySearch {
	public static int binarySearch(int[] arr, int target) {
		Arrays.sort(arr);
		int s = 0;
		int e = arr.length - 1;
		int mid;

		while (s <= e) {
			mid = (s + e) / 2;
			if (arr[mid] == target) {
				return mid;
			}
			if (arr[mid] < target) {
				s = mid + 1;
			} else {
				e = mid - 1;
			}
		}
		throw new NoSuchElementException("타겟 존재하지 않음");
	}

	public static void main(String[] args) {
		int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
		int target = 6;
		System.out.println(target + "의 인덱스: " + binarySearch(arr, target));
		try {
			target = 11;
			System.out.println(target + "의 인덱스: " + binarySearch(arr, target));
		} catch (Exception e) {
			System.out.println(e);
		}
	}
}

6의 인덱스: 6
java.util.NoSuchElementException: 타겟 존재하지 않음

References::