Search 검색 알고리즘

검색 알고리즘에는 아래 2개 알고리즘이 속해 있다.

  • Linear Search : 선형검색 알고리즘
  • Binary Searh : 이진검색 알고리즘

선형검색 알고리즘 개념

선형 검색 알고리즘은 어떻게 보면 가장 검색을 하기 위한 자연스러운 방식이다.
10 크기의 배열에서 7이라는 데이터를 찾고 싶다면, 0번 인덱스부터 9번 인덱스까지
차례대로 차근 차근 7과 일치하는지 확인해서 순서대로 목표값을 찾는 것이다.
최악의 케이스는 찾는 아이템 7이 배열의 맨 끝에 있거나 아예 없는 경우이다.

Linear Time Complexity

즉, 배열이 커지면 커질수록 선형 검색 시간 또한 길어지는 것인데
이런 것을 Linear Time Complexity(선형 시간 복잡도)라고 한다.
인풋이 많으면 많을수록 수행 시간 역시 선형적으로 증가한다는 의미이다.

Binary Searh

Linear Search에서 발전된 것이 이진 검색 알고리즘, 즉 Binary Searh이다.
어떤 알고리즘은 특정 자료구조에서만 사용할 수 있는데, 이진검색 알고리즘이 그렇다.
앞서 살펴본 선형검색 알고리즘은 어느 배열에서도 사용이 가능하지만,
이진검색 알고리즘은 Sorted Array 자료구조에서만 사용할 수 있다.

Sorted Array

그렇다면 Sorted Array가 뭘까? 정렬된 배열이라는 뜻이다.
그러니까 배열들이 순서대로(ex.작은수~큰수) 정렬된 배열이라는 의미이다.
정렬된 배열에서 검색을 하는 것은 정렬이 안된 경우보다 훨씬 많이 빠르다. Super Fast!
그런데 Sorted Array의 삽입은 정렬이 되지 않은 경우보다 더 많은 시간이 걸린다.
왜냐하면 작은 숫자부터 큰 숫자 순으로 나열된 배열에서 특정 숫자를 삽입하고 싶다면
모든 인덱스를 차례대로 비교해서 크기를 따지고 삽입할 위치를 정해야하기때문이다.
위치를 정하고 나서는 또 다시 해당 공간에 자리를 만들기 위해서 배열을 이동시켜야 한다.
하지만 이렇게 배열에 추가하고 정렬하는 것에 시간을 더 투자한다면
검색을 하는 순간에 큰 보람을 느낄 수 있을정도로 가치가 있다.

이진탐색 알고리즘 개념

이진탐색 알고리즘의 "이진"은 01이 아니라 "하나를 반으로 쪼개는 것"을 의미한다.
첫 인덱스부터 검색하는 선형탐색과 달리 이진탐색은 배열의 정중앙부터 검색을 시작한다.
그리고 정중앙 숫자가 목표 숫자보다 큰지, 작은지를 비교해서 목표보다 크다면
아이템의 왼쪽으로 가고, 목표보다 작다면 아이템의 오른쪽으로 가는 방식이다.

10,000개의 배열이 있을 때 선형탐색 알고리즘을 사용해 검색한다면
최악의 경우 10,000번의 단계를 거쳐야하지만
이진탐색 알고리즘을 사용한다면 최악의 경우라도 14단계로 완료할 수 있다.
이렇게 어떤 알고리즘과 자료구조를 사용하느냐는 정말 중요하다.

검색 알고리즘 정리

이진검색은 거대한 배열을 다룰 때 효과적이지만, 이진검색을 위해서는 정렬을 해야하고
배열을 정렬하는 것과, 정렬된 배열에서 삽입/삭제를 할 때에는 시간이 많이 소요된다는 상충점이 있다.

🙏 Reference

0개의 댓글