Contents
이진검색이란 ?이진검색이란 ?
배열을 반씩 잘라가며 중앙값을 기준으로 목표를 찾아가는 방법
중앙값의 위치는 최솟값 + (최댓값 - 최솟값) / 2 로 정의
mid = start + ((end - start) / 2)
세 가지 기본 원칙
- 중앙값보다 작으면 왼쪽에서 찾는다
- 중앙값보다 크면 오른쪽에서 찾는다
- 중앙값과 같으면 찾은것이다
시간 복잡도 = O(log n)
선형탐색(풀스캔)은 시간 복잡도가 O(n)으로 비효율적이다.
그렇지만 배열 안에서 찾는 요소의 수가 여러개일 때에는
분포도가 10~15% 이상인 경우는 랜덤액세스 비용때문에 선형탐색(풀스캔)이 더 좋다
public class BinarySearch {
public static void main(String[] args) {
// N = 21
// 시간복잡도 log2(N) -> log2(21) -> 4.xxx
// 이진 검색 => 반드시 정렬이 되어 있어야 한다.
// 21 / 2*2*2*2*2 -> logn -> log21
int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
int N = arr.length;
final int target = 2;
int start = 0;
int end = N - 1;
int mid;
int round = 1;
while (true) {
// 1 회전
mid = start + ((end - start) / 2); // 기대값 7
System.out.println("mid: " + mid);
if (arr[mid] == target) {
System.out.println(round + "회전 : " + target + "값은 " + mid + "번지에 있습니다");
break;
}
if (arr[mid] < target) { // 기대값 start 5, end 8
start = mid + 1;
}
if (arr[mid] > target) {
end = mid - 1;
}
System.out.println(round + "회전 start : " + start);
System.out.println(round + "회전 end : " + end);
round++;
}
System.out.println("시간복잡도 : " + (Math.log(N) / Math.log(2)));
}
}Share article
