🤔개념
이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다.
장점 : 검색이 반복될 때마다 목표값을 찾을 확률이 두배가 되므로 속도가 빠릅니다.
단점 : 검색 원리상(중간 값을 찾아야 하기에) 정렬된 리스트에만 사용할 수 있습니다.
📌 동작 방식
- 배열의 중간 값을 임의의 값으로 선택
- 중앙 값과 찾고자 하는 값의 크고 작음을 비교
- 중앙 값 = 찾는 값 : 값을 찾았으니 검색 종료
- 중앙값 > 찾는 값 : 중앙값 기준 배열의 왼쪽 구간을 대상으로 탐색
- 중앙값 < 찾는 값 : 중앙값 기준 배열의 오른쪽 구간을 대상으로 탐색
- 값을 찾거나 간격이 0이 될때까지 반복
- 리스트에서 검색할 값과 같은 요소 발견한 경우(검색 성공)
- 검색할 범위가 더 이상 없을 경우(검색 실패)
📌 동작 방식 알고리즘 설명
0. 선행 조건
배열 : arr[1,2,3,4,5,6,7]
찾는 값 : 5 
1. 배열의 중간 값을 임의의 값으로 선택
key(찾는 값) : 5
mid(중앙 값) : 4
검색 범위 : 1, 2, 3, 4, 5, 6, 7
2. 중앙 값과 찾고자 하는 값의 크고 작음을 비교
2-1. 중앙값(4) < 찾는 값(5) : 중앙값 기준 배열의 오른쪽 구간을 대상으로 탐색
(값을 찾거나 간격이 0이 될때까지 반복)
key(찾는 값) : 5
mid(중앙 값) : 6
검색 범위 : 4, 5, 6, 7 
2-2 중앙값(6) > 찾는 값(5) : 중앙값 기준 배열의 왼쪽 구간을 대상으로 탐색
(값을 찾거나 간격이 0이 될때까지 반복)
key(찾는 값) : 5
mid(중앙 값) : 5
검색 범위 : 4, 5, 6 
2-3 중앙 값 = 찾는 값 : 값을 찾았으니 검색 종료
3. 값을 찾거나 간격이 0이 될때까지 반복
💡 TIP. 중앙 값 계산식
int mid = (low + high) / 2
//만약 배열의 크기가 커지게 된다면
//low + high를 했을 때 int 범위를 벗어날 수 있기에 이렇게 사용하는편이 좋음
int mid = low + (hight-low) / 2⏱ 시간 복잡도 및 빅오 표기
Θ(log n)💻 이진 탐색 알고리즘 구현 with JAVA
public int binarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
int mid = 0;
while (start <= end) {
mid = (start + end) / 2;
if (target == arr[mid]) {
return mid;
}else if (arr[mid] < target) {
start = mid + 1;
}else if (target < arr[mid]) {
end = mid - 1;
}
}
throw new NoSuchElementException("can't find target.");
}이진탐색 예제
출처
💻 .net, Spring