배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조이다.
컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근한다.
만약 어떤 값이 배열 안에 속해 있는지를 찾아 보기 위해서는 배열이 정렬되어 있는지
여부에 따라 다른 방법을 사용할 수 있다.
예를 들어 10개의 상자 안에 숫자들이 들어있는데 여기서 50의 숫자를 찾아야 한다고 가정해보자.
1. 선형 검색
배열이 정렬되어있지 않은 경우.
배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지를 검사한다.
아래 의사코드와 같이 나타낼 수 있다.
For i from 0 to n–1
If i'th element is 50
Return true
Return false말 그대로 처음부터 끝까지 상자를 열어보면서 50의 숫자를 찾는 방법이다.
2. 이진 검색
만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며
그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로
이동을 반복하면 된다.
아래 의사코드와 같이 나타낼 수 있다.
If no items
Return false
If middle item is 50
Return true
Else if 50 < middle item
Search left half
Else if 50 > middle item
Search right half생각해보기
Q. 만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요?
A. 이 경우에는 선형 검색을 쓰는 것이 더 올바른 방법이라고 생각한다.
검색의 속도 측면에서 생각해보면 물론 이진 검색이 빠를 수도 있겠지만,
위의 예시를 보고 생각해봤을 때 이진 검색 방법을 그대로 적용한다면 찾아야하는 항목이 있는
범위를 그냥 지나칠 수도 있는 오류를 범할 수 있기 때문이다.
그런 오류를 범한다면 일을 두 번, 세 번 혹은 그 이상 반복하는 경우도 생길 수 있기 때문에
선형 검색 방법을 쓰는게 옳다고 생각한다.
Ref.
Edwith_boost course
