3. 정렬된 배열과 이진검색

선형검색(Linear Search)

(왼쪽) 일반 배열 / (오른쪽) 정렬된 배열

 

모든 요소들이 내림차순 또는 오름차순으로 정렬되어 있는 상태의 배열과 기존 배열이 있다.

이때 50을 각각의 배열에서 찾을 때 더 효율적인 배열은 ?

 

기존배열에서 50이라는 요소를 찾기 위해서는 모든 요소를 순회해야하는 반면

50이라는 요소를 배열안에서 찾을 때, 타깃숫자가 순회하는 숫자보다 작다면 순회를 멈춘다.

즉 정렬된 배열은 기존 배열보다 순회하는데 있어서 효율적이다.

[단 찾는 요소가 배열의 마지막 일 때에 시간 복잡도는 같다.]

 

 

선형검색

 

정렬된 배열에 요소를 추가할 경우, 추가하려는 요소와 기존 배열의 요소들을 비교한 후, 추가된다.

이때 배열을 추가하기 위한 최악의 상황은 모든 요소를 순회한 후 추가해야 하기 때문에 효율적이라고 보기 어렵다.

 

 

이진검색 (Binary search)

이진검색

Q. 1부터 9까지 숫자 중 친구가 생각하는 숫자를 최소의 질문으로 맞추기 위한 방법은?

 

정렬된 배열이라고 했을 때, 배열의 중간의 숫자를 확인한다.

확인한 숫자가 찾으려고 하는 숫자보다 크다면 중간의 숫자가 최소값이되고,

배열의 마지막 인덱스의 있는 값이 최대값이 된다.

반대로 확인한 숫자가 타깃 숫자보다 작다면 확인한 숫자가 최대값이 된다.

이렇게 계속 반복하다 보면 결국에 구하는 값이 나온다.

 

 

결론

선형탐색과 이진탐색의 시간복잡도 비교 그래프

1부터 100이 들어 있는 배열을 검색할 때 최대 단계의 수는 ?

선형검색은 100단계 / 이진검색은 7단계

 

선형검색은 원소의 수가 두배로 증가하면 단계의 수 역시 두배로 증가한다.

반면 이진검색은 원소의 수 두배로 증가해도 단계의 수가 한 단계만 늘어난다.

배열 검색 시, 이진검색이 선형검색보다 더 효율적이라는 것을 볼 수 있다.