정렬된 리스트 형태로 주어진 원소에 대해 탐색 대상의 크기를 절반씩 줄여 가면서 탐색 키를 가진 원소를 찾는 방식
리스트는 일차원 배열에 저장된 것으로, 정렬은 오름차순 정렬로 가정
public class BinarySearch {
/**
* 이진 검색 메서드
*/
static int binarySearch(int[] array, int length, int key) {
int left = 0; // 검색 범위의 첫 인덱스
int right = length - 1; // 검색 범위의 끝 인덱스
do {
int center = (left + right) / 2; // 중앙 요소의 인덱스
if (array[center] == key) { // 중앙 요소의 값과 key 값이 같은 경우
return center; // 검색 성공
} else if (array[center] < key) { // 중앙 요소의 값보다 key 값이 큰(오른쪽에 있는) 경우
left = center + 1; // 검색 범위를 뒤쪽 절반으로 축소
} else { // 중앙 요소의 값보다 key 값이 작은(왼쪽에 있는) 경우
right = center - 1; // 검색 범위를 앞쪽 절반으로 축소
}
} while (left <= right);
return -1; // 검색 실패
}
public static void main(String[] args) {
int[] array = {15, 27, 39, 77, 92, 108, 121};
int key = 39; // 키 값
int index = binarySearch(array, array.length, key); // 배열 array에서 키 값이 key인 요소를 검색
if (index == -1) {
System.out.println("값이 존재하지 않습니다.");
} else {
System.out.println(key + "을(를) 찾았습니다!");
}
}
}
static int binarySearch(int[] array, int length, int key) {
int left = 0; // O(1)
int right = length - 1; // O(1)
do {
int center = (left + right) / 2; // O(log n)
if (array[center] == key) { // O(log n)
return center; // O(n)
} else if (array[center] < key) { // O(log n)
left = center + 1; // O(log n)
} else {
right = center - 1; // O(log n)
}
} while (left <= right); // O(log n)
return -1; // O(1)
}
O(1) + O(1) + O(log n) + O(log n) + O(1) + O(log n) + O(log n) + O(log n) + O(log n) + O(1) = O(log n)
입력이 정렬된 리스트에 대해서만 적용 가능
입력 데이터의 정렬 여부를 알 수 없을 경우 → 초기화 연산 이용
초기화 연산 : O(nlogn)
이진 탐색 수행의 대전제는 원소들이 정렬되어 있다는 것
삽입 연산 : O(n)
삽입이 끝났을 때 정렬 상태가 유지되어야 함
삭제 연산 : O(n)
삭제가 끝났을 때 정렬 상태가 유지되어야 함
📖 참고
- 이관용, 김진욱(2024). 알고리즘. 한국방송통신대학교출판문화원
- Bohyoh Shibata. (2020). Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바편(강민 옮김). 이지스퍼블리싱