초코레

오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다. 알고리즘의 복잡도는 O(log n) 이다. 복잡도의 대소 관계 : 1 < log n < n < n log n < n^2 < n^3 < n^k < 2^n JAVA는 배열에서 이진 검색을 하는 java.util.Arrays 클래스의 binarySearch 메서드로 제공한다. 모든 자료형 배열에서 이진 검색을 할 수 있도록 오버로딩되어 있다. [검색 성공] : 넘긴 값과 일치하는 요소의 인덱스를 반환한다. 일치하는 요소가 여러 개라면 무작위의 인덱스를 반환한다. [검색 실패] : 삽입 포인트를 x라고 할 때 -x - 1을 반환한다. ..