linearSearch.md

선형 검색(Sequential/Linear Search)

원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘

원소의 값이 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법입니다.

• 배열에 원하는 값이 존재할 때 조건을 판단하는 횟수 = 배열 원소의 개수/2 번 ?
• 배열에 원하는 값이 존재하지 않을 때 조건을 판단하는 횟수 = n+1 번 or n 번

# while문으로 작성한 선형 검색 알고리즘
i = 0
while True:
    # 검색 실패
	  if i == len(a):
        return -1
    # 검색 성공(찾은 원소의 인덱스는 i, 맨 처음 발견한 원소의 index만 반환)
    if a[i] == key:
        return i
    i += 1

보초법(Sentinel method)

• 선형 검색의 단점
  • 반복할 때마다 2가지 종료 조건을 매번 체크합니다. ⇒ 비용⬆️

검색할 값을 배열의 맨 끝에 추가해서 보초로 사용하는 방법입니다. 선형 검색에서 매번 2가지 종료 조건을 체크하는데 사용하는 비용을 반으로 줄여줍니다.

• if i == len(a) ⇒ 수행할 필요X
• if a[i] == key
• 질문. 왜 실습3-3에서는 보초법을 사용해서 판단 횟수를 줄인 후에 다시 len(seq)에 대한 판단문을 수행하는지, 해당 구문이 있으면 판단횟수가 안 줄어든거 아닌가..!
• 질문. copy.deepcopy로 복사를 하는 이유? 복사하지 않고 수행했을 때 차이가 있는지
  • 참고 링크: [Python]Shallow copy & Deep copy