선형검색 알고리즘 (Linear Search)

10개의 데이터가 있는 배열에서 '7'을 찾을 때 1번 아이템부터 차례대로 7이 맞는지 확인을 한다. (끝까지 순서대로 차근차근) 이렇게 순서대로 목표값을 찾는걸 선형검색 알고리즘 (Linear Search)라고 한다.

찾는 아이템이 배열 맨 마지막에 있거나 해당 배열에 아예 없는 경우 가장 최악이다.

이진검색 알고리즘 (Binary Search)

선형검색 알고리즘의 단점을 개선한게 이진검색 알고리즘 (Binary Search)이다. 그러나 이진검색 알고리즘을 모든 배열에 쓸 수 있는 것은 아니다.
이진검색 알고리즘은 정렬된 배열 (sorted array)에서만 사용 가능하다.

정렬된 배열 (sorted array)

sorted array란 배열들이 순서대로 정렬된 경우를 의미한다.

정렬된 배열에 아이템을 추가하는 것은 정렬이 안된 경우보다 시간이 더 걸리지만, 정렬된 배열에서 아이템을 검색하는건 매우 빠르다.

2 5 7 8로 정렬된 배열이 있을 때 '8'을 추가하려면 해당 배열에서 8보다 큰 아이템을 찾아야 한다. 해당 아이템을 찾은 후 '8'을 해당 아이템의 왼쪽에 추가하게 된다.
즉, 인덱스 0부터 '8'보다 큰지 작은지를 각각 비교해야 하고, 큰 아이템을 찾은 경우 오른쪽에 있는 아이템들을 움직여야한다.

이진검색

이진검색에서 이진이란 0과 1을 뜻하는 것이 아닌, 반으로 쪼개는 것을 의미한다. 즉 하나를 두 개로 쪼개는 것을 뜻한다.

이진검색은 선형 검색과 달리 인덱스 0인 처음부터 검색을 하지 않고 중간(정가운데)에서 시작한다.
중간 값이 찾고 있는 아이템보다 크다면 중간 값의 왼쪽으로 가고, 작다면 중간 값의 오른쪽으로 간다.

1~10이 있는 배열에서 9를 찾는 경우 중간값인 5에서 검색이 시작된다. 9는 5보다 크므로 오른쪽으로 간다. 오른쪽에서의 중간값을 찾아 해당 프로세스를 반복하게 된다.