선형 검색(Linear Search)은 배열에서 특정 값을 찾아내는 탐색 기법으로, 가장 단순하고 기본적인 검색 방법입니다.
이 기법은 다음과 같은 방식으로 동작합니다.
찾고자 하는 값을 배열의 모든 요소와 하나씩 순서대로 비교합니다.
값을 찾으면 해당 요소의 인덱스를 반환합니다.
배열 전체를 확인해도 해당 요소가 존재하지 않는다면 -1 또는 관련 메시지를 반환합니다.
의사코드(Pseudocode)
linearSearch(int array[], int value):
for i=0 to len(array):
if(array[i]==value):
Element is Present
//for 루프 종료 후
Element Not Present // 배열 전체에서 요소를 찾지 못한 경우예제 코드
def linearSearch(arr,value):
for i in range(len(arr)):
if(arr[i]==value):
return i
return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=5
a=linearSearch(array,value)
if(a==-1):
print("Element not present")
else:
print("Element present at index",a)실행 결과
Element present at index 4
시간 복잡도
선형 검색의 최악의 경우 시간 복잡도는 O(n)입니다. 최악의 경우는 찾으려는 요소가 배열의 마지막 인덱스에 있거나 아예 존재하지 않을 때 발생합니다.
반면 최선의 경우 시간 복잡도는 O(1)입니다. 찾으려는 요소가 배열의 첫 번째 인덱스에 있는 경우가 이에 해당합니다.
개선된 선형 검색
선형 검색의 최악의 경우 시간 복잡도는 O(n/2)까지 개선할 수 있습니다. 왼쪽(left)과 오른쪽(right) 두 개의 포인터를 사용해 한 번의 반복에서 두 개의 비교를 동시에 수행하는 방식으로, 반복 횟수를 절반으로 줄일 수 있습니다.
예제 코드
def linearSearch(arr,value):
left=0
right=len(arr)-1
while(left<=right):
if(arr[left]==value):
return left
elif(arr[right]==value):
return right
left+=1
right-=1
return -1
array=[1,2,3,4,5,6,7,8,9,10]
value=10
a=linearSearch(array,value)
if(a==-1):
print("Element not present")
else:
print("Element present at index",a)실행 결과
Element present at index 9
위 예제에서 마지막 인덱스에 위치한 요소는 첫 번째 반복만에 찾아졌습니다. 앞서 살펴본 기본 방식이라면 이 요소를 찾는 데 10번의 반복이 필요했을 것입니다.
또한 요소를 찾지 못하는 경우에도 두 번째 방식의 총 반복 횟수는 n/2이므로, 최악의 경우 시간 복잡도는 O(n/2)가 됩니다.
선형 검색은 얼마나 유용할까?
선형 검색은 이진 검색(Binary Search)처럼 더 나은 시간 복잡도를 제공하는 우수한 탐색 알고리즘이 존재하기 때문에 실무에서는 거의 사용되지 않습니다. 특히 입력 배열의 크기가 클수록 효율이 크게 떨어지므로 대용량 데이터에는 적합하지 않습니다.