Python에서 선형 검색을 위한 프로그램 작성

선형 검색은 배열에서 특정 값을 검색하는 검색 기술입니다. 이것은 가장 간단한 검색 기술입니다.

이 검색 기술에서

• 검색할 값은 배열의 모든 요소와 비교됩니다.

• 값을 찾으면 해당 요소의 인덱스를 반환합니다.

• 특정 요소가 배열 전체에 존재하지 않으면 -1 또는 일부 관련 문자열 메시지를 반환합니다.

의사 코드

linearSearch(int array[], int value):
   for i=0 to len(array):
      if(array[i]==value):
         Element is Present
   //outside for loop
   Element Not Present // element not found in the whole array

예시

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)로 향상될 수 있습니다. 이것은 왼쪽과 오른쪽의 두 포인터를 사용하여 한 번에 두 개의 비교를 수행하여 수행할 수 있으므로 선형 검색의 최악의 경우 시간 복잡성을 O(n/2)로 줄일 수 있습니다.

예시

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)입니다.

선형 검색이 얼마나 유용한가요?

선형 탐색은 더 나은 시간 복잡성을 제공하는 이진 탐색과 같은 더 나은 탐색 알고리즘이 있기 때문에 거의 사용되지 않습니다. 선형 검색은 큰 입력 배열에 대해 효율적이지 않습니다.