Algorithms. 선형 검색

 

Information

순차 검색 알고리즘(sequential search algorithm), 또는 선형 검색 알고리즘(linear search algorithm)은 리스트에서 특정한 값을 찾는 알고리즘의 하나다. 이것은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 비효율적이지만, 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다.

 

 

---

선형 검색

• 순차 검색 
• 선형으로 나열되어 있는 데이터를 순차적으로 검색하여 원하는 값을 찾음
• 검색 성공 또는 검색 실패

 

 

 

구현

 

1

nums = [0, 4, 2, 1, 8, 5, 7, 3, 9, 6]


def sequentialSearch(arr, key):
    n = 0
    answer = 0
    while True:
        if n == len(arr):
            answer = -1  # 검색 실패로 종료를 나타냄
            break

        elif arr[n] == key:
            answer = n
            break

        n += 1
    return answer

print(sequentialSearch(nums, 7)) # 출력 인덱스 6

 

2

nums = [0, 4, 2, 1, 8, 5, 7, 3, 9, 6]


def sequential(array, value):
    for i in range(len(array)):
        if array[i] == value:
            return i
    return False	# 검색 실패하면 False 출력

print(sequential(nums,6)) # 출력 인덱스 9

 

 

 

 

보초법

• Sentinel method
• Sentinel Linear Search
  • 마지막 인덱스에 찾으려는 값을 추가해 보초 값으로 사용하여 찾는 횟수를 간략화 한다.
  • 마지막 인덱스 이전에 검색되면 성공
  • 마지막 인덱스가 검색되면 실패

 

 

 

구현

 

def sentinelSearch(arr, key):

    arr.append(key)
    n = 0
    answer = 0

    while True:
        if arr[n] == key:
            if n != len(arr) - 1:
                answer = n
                break
            else:
                answer = -1   # n이 마지막 인덱스면 검색 실패
                break
        n += 1
    return answer

print(sentinelSearch(nums, 11))	# 출력 -1

 

---

예시

2021.11.09 - [스터디(zero-base)/알고리즘] - Algorithms. 선형 검색 예시

Algorithms. 선형 검색 예시

 

 

도움

https://www.geeksforgeeks.org/sentinel-linear-search/