[JAVA] 이진 검색(binary search), Arrays.binarySearch

이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 입니다.

이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있습니다.

---

이진 검색 예시

오름차순으로 정렬된 배열에서 39를 검색하는 과정을 생각해 보겠습니다.

먼저 배열의 중앙에 위치한 요소인 31부터 검색을 시작합니다.

검색하려는 값인 39는 중앙 요소(31)보다 큰 값입니다.

따라서 검색 대상을 뒤쪽([6]~[10])으로 좁힐 수 있습니다. 

그런 다음 검색 범위의 중앙에 요소한 위치인 68이 원하는 값인지 확인합니다. 

검색하려는 39보다 큰 값입니다. 

이제 검색해야 하는 대상은 2개 입니다. 

두 인덱스 6과 7의 중앙값은 (6+7)/2 로 6이 되므로 39와 비교해 줍니다.

원하는 값과 일치하므로 검색 성공입니다!

 

이진 검색 종료 조건

조건 1 : 배열의 중앙값과 원하는 값이 일치하는 경우

조건 2 : 검색 범위가 더 이상 없는 경우

 

이진 검색 예제

 

Arrays.binarySearch

JAVA는 배열에서 이진 검색을 하는 메소드를 표준 라이브러리로 제공합니다.

java.util.Arrays 클래스의 binarySearch 메소드는 다음과 같은 장점이 있습니다.

 

장점 1 : 이진 검색 메소드를 직접 코딩할 필요가 없다.

          ★ 오름차순으로 정렬된 배열 a를 가정하고, 키 값이 key 인 요소를 이진 검색하는 메소드 입니다.

장점 2 : 모든 자료형 배열에서 검색할 수 있다.

          ★ binarySearch 메소드는 자료형에 따라 오버로딩 되어있습니다.

     

검색에 성공한 경우

key와 일치하는 요소의 인덱스를 반환합니다. 

만약 일치하는 요소가 여러 개 있다면 무작위의 인덱스를 반환합니다.

 

검색에 실패한 경우

음수의 숫자를 반환합니다.

 

Arrays.binarySearch 예제

• 기본 자료형 배열에서 binarySearch 메소드로 검색하기

• 객체의 배열에서 binarySearch 메소드로 검색하기

 

---

이상으로 이진 검색(binary search)에 대해 알아보았습니다.