정렬되지 않은 배열에서 이진 검색과 선형 검색 속도 비교

edwith 강의 마지막에 생각해보기 질문이 다음과 같았다.

만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요?

[LECTURE] 1) 검색 알고리즘 : edwith

내가 현재 가지고 있는 자료구조와 알고리즘 책에서는 이진 검색의 '전제'가 '정렬된 데이터'에서 검색하는 것이기 때문에 문제가 성립하지 않는다. 하지만 무시하고 진행시키면 속도는 어떻게 측정할 수 있을까?

선형 검색의 경우 그냥 처음부터 검사하면 되지만, 이진 검색의 경우 문제가 생긴다. 이진검색은 중앙값을 검색하고, 찾으려는 값과 대소를 비교하여 다음 중앙값을 검색하는, 순차적으로 검색 대상을 절반씩 좁히는 과정이다. 그런데 데이터가 정렬되어 있지 않으니, 검색 대상을 좁혀도 의미가 없다. 즉, 계속 허탕을 친다.

package chap03;
import java.util.Scanner;
// 이진 검색 

class BinSearch {
	// 요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색합니다.
	static int binSearch(int[] a, int n, int key) {
		int pl = 0;			// 검색 범위의 첫 인덱스
		int pr = n - 1;		// 검색 범위의 끝 인덱스

		do {
			int pc = (pl + pr) / 2;		// 중앙 요소의 인덱스
			if (a[pc] == key)
				return pc;				// 검색 성공!
			else if (a[pc] < key)
				pl = pc + 1;			// 검색 범위를 뒤쪽 절반으로 좁힘
			else
				pr = pc - 1;			// 검색 범위를 앞쪽 절반으로 좁힘
		} while (pl <= pr);

		return -1;						// 검색 실패!
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.print("요솟수：");
		int num = stdIn.nextInt();
		int[] x = new int[num];				// 요솟수가 num인 배열

		System.out.println("오름차순으로 입력하세요.");

		System.out.print("x[0]：");			// 첫 요소 입력
		x[0] = stdIn.nextInt();

		for (int i = 1; i < num; i++) {
			//do {
				System.out.print("x[" + i + "]：");
				x[i] = stdIn.nextInt();
			// }  while (x[i] < x[i - 1]);		// 바로 앞의 요소보다 작으면 다시 입력
		}

		System.out.print("검색할 값：");		// 키값을 입력
		int ky = stdIn.nextInt();

		int idx = binSearch(x, num, ky);	// 배열x에서 값이 ky인 요소를 검색

		if (idx == -1)
			System.out.println("그 값의 요소가 없습니다.");
		else
			System.out.println(ky+"은(는) x[" + idx + "]에 있습니다.");
	}
}

* 위 코드에서 중간 for문 안 do while문의 주석을 제거하면 정상적인 이진 검색 알고리즘이다. (출처: 책 <자료구조와 함께 배우는 알고리즘 입문 자바편>)

수학적으로 계산은 못하겠지만, 정렬되지 않은 데이터에서 이진 검색의 경우, 일단 '전제에서 어긋나며', 전제를 무시하고 검색을 진행하더라도 금방 실패한다. 이진 검색 방식으로는 데이터의 존재 유무도 '확률'적으로 알아야 한다. 따라서 좋은 알고리즘이라고 할 수 없고, 속도 비교도 대부분의 경우, 선형 검색이 우위에 있을 것이다.