선형탐색(linearSearch)
배열에서 특정 값을 찾기 위해 순차적으로 배열의 각 요소를 검색하는 방법입니다. 자바스크립트에서 대표적인 선형탐색 중 하나는 indexOf() 가 있습니다.
선형 탐색은 배열의 첫 번째 요소부터 마지막 요소까지 차례대로 검색하면서 원하는 값을 찾습니다. 만약 원하는 값이 있다면 해당 값의 인덱스를 반환하고, 찾지 못했다면 -1을 반환합니다.
코드
아래 예시에서는 linearSearch() 함수가 배열과 찾을 값을 인자로 받습니다. 함수는 배열을 처음부터 끝까지 순회하면서 원하는 값을 찾습니다. 만약 찾고자 하는 값이 있다면 해당 값의 인덱스를 반환하고, 찾지 못했다면 -1을 반환합니다.
function linearSearch(arr, value) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === value) {
return i; // 값을 찾았을 경우 해당 인덱스를 반환
}
}
return -1; // 값을 찾지 못했을 경우 -1 반환
}
// 0 1 2 3 4
const myArr = [1, 2, 3, 4, 5];
console.log(linearSearch(myArr, 3)); // 2
console.log(linearSearch(myArr, 6)); // -1시간복잡도
- 최악의 경우: O(n)
선형 탐색에서 최악의 경우는 배열의 끝까지 모든 요소를 비교해야 하는 경우입니다. 이 경우에는 n개의 요소를 모두 비교해야 하므로, 시간복잡도는 O(n)이 됩니다.
- 보통의 경우: O(n)
배열의 중간 부분에 찾고자 하는 요소가 있는 경우, 평균적으로 n/2개의 요소를 비교해야 합니다. 따라서 시간복잡도는 O(n)입니다.
- 최적의 경우: O(1)
만약 배열의 첫 번째 요소가 찾고자 하는 요소인 경우, 첫 번째 요소와 비교하면서 바로 찾을 수 있습니다. 이 경우에는 한 번의 비교만으로 요소를 찾을 수 있으므로, 시간복잡도는 O(1)이 됩니다.
위와 같이 선형 탐색의 시간복잡도는 배열의 크기에 비례하므로, 배열이 커질수록 탐색 시간이 증가합니다. 따라서 큰 배열에서 탐색을 수행할 경우, 다른 알고리즘을 고려해볼 필요가 있습니다.
공간복잡도
선형 탐색(Linear Search)의 공간복잡도는 입력 데이터와 관계없이 항상 O(1)입니다. 이는 추가적인 메모리 공간을 필요로 하지 않기 때문입니다.
선형 탐색에서는 주어진 배열에서 순차적으로 요소를 찾아가면서 일치하는 요소를 찾기 때문에, 추가적인 데이터 구조나 배열을 만들 필요가 없습니다. 따라서 선형 탐색의 공간복잡도는 최악, 보통, 최적의 경우 모두 O(1)입니다.
선형탐색의 이점과 한계
선형 탐색은 배열이 정렬되어 있지 않거나, 배열의 크기가 작을 경우에 유용합니다. 하지만 배열의 크기가 매우 크거나 정렬되어 있다면 이진 탐색(Binary Search)과 같은 다른 알고리즘을 사용하는 것이 더욱 효율적일 수 있습니다.