이진 탐색

Binary Search

이진 탐색은 오름차순으로 정렬되어 있는 리스트 내에서 특정 값의 index를 찾는 알고리즘이다.

구현 방식

배열의 중간 인덱스를 찾는다.

중간 인덱스를 기준으로 배열을 반으로 나눈다.

나눠진 절반의 리스트에서 타겟을 찾는다.

중간 값이 타겟과 같으면 종료
중간 값이 타겟보다 크면 중간 값 기준 오른쪽 절반의 리스트에서 탐색
중간 값이 타겟보다 작으면 중간 값 기준 왼쪽 절반의 리스트에서 탐색
타겟을 찾아내거나 더 이상 탐색이 안될 때까지 반복

시간복잡도

알고리즘의 작동 방식을 보면 계속 반으로 나눠가면서 반복하기 때문에 worst case에서도 O(logN)의 시간복잡도를 가진다는 것을 알 수 있다. 시간복잡도 차트에서 Fair 정도의 수준이라 써먹을만 하다.

실제 사용 예시

Java의 이진 탐색(Binary Search) 메서드 사용하기 (Comparator 구현)

Java의 기본 라이브러리에는 Binary Search 메서드가 내장되어 있습니다. java.util.Arrays 클래스에 존재합니다. 다양한 자료형의 배열을 사용할 수 있에 오버로딩되어 있는데, 본 아티클에서는, 제너릭스로 구현된(자료형에 구애받지 않고 사용할 수 있게 구현) 메서드를 사용해볼 것입니다.. 새로운 자료형(클래스) 제너릭스로 구현 //--- 신체검사 데이터 ---// class PhyscData { private final String name; // 이름 private final int height; // 키 private final double vision; // 시력 //--- 생성자(constructor) ---// public PhyscData(String name, int he..

Java의 이진 탐색(Binary Search) 메서드 사용하기 (Comparator 구현)

https://woojin.tistory.com/80

Java의 이진 탐색(Binary Search) 메서드 사용하기 (Comparator 구현)

자바에는 Arrays.binarySearch()라는 메서드가 이미 존재한다.

새로 만들어낸 클래스의 경우에는 비교기준이 없는 상태이기 때문에 위의 예시처럼 Comparator를 구현해줘야 한다.

binarySearch() 메서드는 이미 정렬이 되어 있는 배열을 인자로 넣는다고 가정이 되어 있기 때문에 정렬을 한 후 사용해주면 된다.