- Published on
검색 알고리즘 : 선형 검색과 이진검색 알고리즘
- Authors
- Name
- Bora Choi
검색 알고리즘
검색 알고리즘하면 구글이나 네이버의 검색알고리즘을 떠올리기 쉽다. 물론 구글이나 네이버는 더욱 복잡한 알고리즘을 사용하겠지만 오늘은 데이터 리스트에서 특정 데이터를 찾는 알고리즘에 대해 다루려고 한다.
대표 알고리즘인 선형검색과 이진검색 알고리즘에대해 알아보고 이 두가지 알고리즘을 비교해보자!
선형검색 알고리즘이란?
여러값이 있는 리스트에서 특정한 값을 찾는 알고리즘으로 리스트의 처음부터 비교하여 특정값을 찾아가는 방식이다. 특징으로는 어떠한 리스트(정렬되어있지 않은 경우)에서도 사용 할 수 있는 알고리즘이다. 단, 리스트의 요소를 하나하나 비교하므로 리스트의 길이가 길수록 효율이 떨어진다.
의사코드 작성하기
선형검색 알고리즘을 코드로 작성하기 전에 의사코드로 정리해보자!
배열과 찾고자하는타겟을 받는 함수를 작성한다.배열의 첫번째 요소부터마지막 요소까지 반복문을 실행한다.배열의 요소와타겟이 같으면 해당인덱스를 반환한다.
- 반복문 실행이 끝날때까지 함수가 종료되지 않으면
-1을 반환한다.
실제 코드로 작성하기
의사코드를 바탕으로 코드로 나타내보자!
function linearSearch(arr: number[], target: number): number {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) return i
}
return -1
}
선형검색의 효율성
선형검색에서 찾고자 하는 값이 리스트의 첫번째에 있다면 최고의 효율성을 가질것이다 이때 시간복잡도는 O(1)이 된다.
그러나 리스트의 가장 마지막에 위치한다면 시간복잡도는 O(N)이다.
이진검색 알고리즘이란?
정렬된 리스트에서 특정한 값을 찾는 검색 알고리즘으로 중간값과 찾고자 하는 값을 비교하는 방식이다.
중간값이 찾고자하는 값보다 크면 그 값을 새로운 최댓값이 되고, 작으면 그 값은 새로운 최솟값이 된다.
특징으로는 정렬된 리스트일때만 알고리즘을 사용할 수 있다는 점이다. 정렬되지 않았을 경우 알고리즘의 효율성이 없다.
의사코드 작성하기
이진검색 알고리즘을 코드로 작성하기 전에 의사코드로 정리해보자!
*배열은 숫자배열을 받는다고 가정한다.
정렬된 배열과타겟을 받는 함수를 작성한다.시작 인덱스와끝 인덱스를 담는 변수를 선언한다.시작 인덱스가끝 인덱스와 같지 않을 때까지 반복문을 실행한다.시작 인덱스와끝 인덱스의평균값을 변수로 선언한다.타겟이평균값보다 크면시작 인덱스값을중간점값으로 변경한다.타겟이평균값보다 작으면끝 인덱스값을중간점값으로 변경한다.타겟이평균값과 같으면인덱스값를 반환한다.
- 반복문실행이 끝날때까지 함수가 종료되지 않으면
-1을 반환한다.
실제 코드로 작성하기
의사코드를 바탕으로 코드로 나타내보자!
function binarySearch(arr: number[], target: number): number {
let start = 0
let end = arr.length - 1
while (start <= end) {
let middle = Math.ceil((start + end) / 2)
if (target === arr[middle]) return middle
else if (target > arr[middle]) start = middle + 1
else end = middle - 1
}
return -1
}
이진검색의 효율성
이진검색의 경우 첫번째 평균값과 타겟값이 같았을때 가장 효율적일 것이다 이때 시간복잡도는 O(1)이 된다.
하지만 최악의 상황에서의 시간복잡도는 O(logN)이다.
이진 검색알고리즘은 사실 일상생활에서도 활용(?)할 수 있는데 바로 바로 술게임에서다.🍻
술 게임중 병뚜껑의 숫자 맞추기 게임에 이진 검색알고리즘을 활용할 수 있다!
일반적으로 소주병은 1~50까지의 숫자이므로 이진 알고리즘의 시간복잡도로 계산해보면
log2(50) = 5.64385619 최대 5.6번만에 답을 맞출 수 있다!
선형검색과 이진검색 알고리즘 비교
선형검색과 이진검색을 한눈에 비교할 수 있도록 표로 정리해보았다.
| - | 선형검색 | 이진검색 |
|---|---|---|
| 데이터 구조 | 연결리스트 혹은 배열 | 정렬된 배열 |
| 최고의시간복잡도 | O(1) | O(1) |
| 최악의시간복잡도 | O(N) | O(logN) |
| 특징 | 순차적으로 탐색 | 분할 정복으로 탐색 |