알고리즘 - 탐색

탐색이란?

 

저장된 정보들 중에서 원하는 값을 찾는 것이다.

 

📍 선형 탐색 알고리즘

 

• 검색 방법 : 주어진 배열에서 값을 검색하는 가장 간단한 방법은 배열의 모든 요소를 살펴보고 원하는 값인지 확인하는 것이다.

 

맨 앞부터 끝까지 차례대로 찾아 나간다.

 

검색할 리스트의 길이가 길면 길수록 비효율적이지만 단순하여 구현이 굉장히 쉽다.

 

정렬되지 않은 리스트에서도 사용할 수 있다.

 

선형 탐색은 데이터를 찾기 위해 데이터를 하나씩 모조리 검사하므로 시간 복잡도는 최악의 경우 O(n)이다.

 

 

📍 이진 탐색 알고리즘

 

• 검색 방법 : 정렬된 리스트에서 특정 값의 위치를 찾는다.

 

처음 중간의 값을 택하여, 해당 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

 

처음 선택한 중앙값이 만약 찾는값보다 크다면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다.

 

검색 원리상 정렬된 리스트에만 사용할 수 있다.

 

검색이 반복될 때마다 목표 값을 찾을 확률이 배가 되므로 속도가 빠르다는 장점이 있다.

 

선형 탐색은 계속해서 반으로 쪼개며 탐색하기 때문에 시간 복잡도가 최악의 경우에도 O(log n)이다.