선형 탐색 알고리즘(Linear Search Algorithm)의 Python 구현

KeeMun·2019년 12월 11일
1

Linear Search Algorithm

1. 문제상황

  여러분은 현재 모든 책이 일렬로 나열되어있는 독특한 도서관에 와 있다.
이때 원하는 책을 찾기 위해서 2가지 선택을 할 수 있다.
1. 앞에서부터 순서대로 책을 찾는다.
1. 사서에게 부탁해 모든책을 정렬한 후 중간부터 '가나다'순 비교해가며 찾는다.

첫 번째 경우의 수가 이번 글의 주제인 Linear Search Algorithm, 즉 "선형 탐색 알고리즘"이다.

2. 탐색 알고리즘

  두 번째는 이진 탐색 알고리즘(Binary Search Algorithm)이다. 정렬된 리스트에 대해서 탐색할 때 대부분의 경우 이진탐색 알고리즘이 훨씬 좋은 성능을 보여준다.
그러나 이진탐색 알고리즘은 리스트가 정렬되어 있어야 한다라는 조건이 있다.

  정렬된 리스트를 사용하기 위해서 비정렬된 리스트를 정렬해주는 알고리즘이 필요하다. 이때 사용하는 정렬 알고리즘은 굉장히 다양한 방식이 있다.
  그러나 선형탐색 알고리즘은 정렬 여부와 상관 없이 값을 찾을 수 있다는 장점이 있고, 구현이 비교적 간단하다.

def linearSearch(arr, target):
   pass

arr = [3,5,6,1,4,7,9,8]
target = 4
print(linearSearch(arr, target))

위에서 linearSrarch(arr) 함수를 완성시켜보자

코드 구현

  먼저 return 값을 정해보자.
1. target 변수 안에 들어있는 값이 arr 리스트 안에 들어있으면 Index 값을 리턴
1. target이 arr에 존재하지 않으면 "Fail" 을 리턴

 def linearSearch(arr, target):
    i = 0
    while i < len(arr):
        if arr[i] == target:
            return i
        i += 1
    return "Fail"

arr = [3,5,6,1,4,7,9,8]
target = 4
print(linearSearch(arr, target))

실행 결과

profile
Hacking & Security University Student

0개의 댓글