Binary Search (이진 탐색)
이진 탐색이란?
- Binary Search는 오름차순으로 정렬된 리스트내에서 특정 값을 찾아내는 알고리즘이다.
- 정렬된 리스트에서 중간값을 기준으로 찾고자 하는 값이 중간값보다 작으면 왼쪽을 탐색, 크면 오른쪽을 탐색하는 과정을 반복하며 특정 값을 찾아낸다.
- Divide and Conquer기법을 사용한다.
- Divide: 중간 값을 기준으로 중간 값보다 작은 리스트, 큰 리스트로 나눈다.
- Conquer:
- 중간값 == 찾는 값, 해당 값 또는 인덱스를 리턴한다.
- 중간값 > 찾는 값, 중간 값보다 작은 서브리스트내에서 검색할 숫자탐색
- 중간값 < 찾는 값, 중간 값보다 큰 서브리스트내에서 검색할 숫자탐색
- Sequential search와 비교하였을 때 일반적으로 탐색 속도가 빠르다.
- 위의 사진을 보면 리스트 내에서 37을 탐색할 때 Sequential은 11번의 탐색을 하며 값을 찾은 것에 비해 Binary의 경우는 3번의 탐색으로 값을 찾았다.
- 하지만 항상 binary가 빠른 곳은 아니다. 예를 들어 위의 예시 리스트에서 1이라는 숫자를 탐색할 경우 sequential은 한번의 탐색 binary search는 4번의 탐색을 해야한다.
Java 구현 코드
public static int binarySearch(List<Integer> arr, int search) {
// 데이터가 1개이고 그 데이터가 찾는 데이터면 True
if (arr.size() == 1 && arr.get(0) == search)
return 0;
// 데이터가 1개인데 그 데이터가 찾는 데이터가 아니면 false
if (arr.size() == 1 && arr.get(0) != search)
return -1;
// 데이터 자체가 없는 경우
if (arr.size() == 0)
return -1;
int middle = arr.size()/2;
if (arr.get(middle) == search)
return middle;
else {
if (arr.get(middle) < search)
return binarySearch(arr.subList(0, middle), search);
else
return binarySearch(arr.subList(middle, arr.size()), search);
}
}🔗 Reference
블로그 이전했습니다. -> https://seongwon.dev/