선형 탐색과 이진 탐색

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

탐색 알고리즘

탐색은 필수적인 연산
- 여러 가지 방법
컬렉션에서 요소를 탐색하는 알고리즘:
- 선형 탐색
- 이진 탐색

선형 탐색

각 요소를 순차적으로 순회

정렬되지 않은 숫자 리스트의 도식 표현.

요소 발견 시
- 알고리즘 중단
- 결과 반환
요소 미발견 시
- 알고리즘 계속

선형 탐색

def linear_search(unordered_list, search_value):

  for index in range(len(unordered_list)):

    if unordered_list[index] == search_value:

      return True

  return False

print(linear_search([15,2,21,3,12,7,8], 8))

True

print(linear_search([15,2,21,3,12,7,8], 800))

False

선형 탐색 - 복잡도

복잡도: $O(n)$

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현.

15 ???

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first라는 변수가 리스트의 첫 번째 위치를 가리킵니다.

15 ???

def binary_search(ordered_list, search_value):
  first = 0

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first라는 변수가 첫 번째 위치를, last라는 변수가 마지막 위치를 가리킵니다.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1


  while first <= last:

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first가 첫 번째 위치를, last가 마지막 위치를, middle이 중간 위치를 가리킵니다.

15 ???

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first, last, middle 변수가 각 위치를 가리키며, 중간 위치의 숫자 12가 노란색으로 표시됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2

    if search_value == ordered_list[middle]:

      return True

    elif search_value < ordered_list[middle]:

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first가 첫 번째 위치를, last가 중간 위치 바로 앞을, middle이 중간 위치를 가리키며, first와 middle 사이의 요소가 초록색으로 표시됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first, last, middle 변수가 각 위치를 가리키며, 중간 위치의 숫자 12가 노란색으로 표시됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first가 중간 위치 바로 다음을, last가 마지막 위치를, middle이 중간 위치를 가리키며, first와 middle 사이의 요소가 초록색으로 표시됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. middle 포인터가 이동하여 first와 last 사이의 요소를 가리키며, first와 middle 사이의 요소가 초록색으로 표시됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. middle 포인터가 이동하여 first와 last 사이의 요소를 가리키며, first와 middle 사이의 요소가 초록색으로 표시됩니다. middle이 가리키는 17이 15와 비교됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. last 포인터가 이동하여 first 포인터와 같은 숫자를 가리킵니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. middle 포인터가 이동하여 first 및 last 포인터와 같은 숫자를 가리킵니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. first, last, middle 포인터가 모두 같은 숫자 15를 가리키며 15와 비교됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

이진 탐색

정렬된 리스트에만 적용

정렬된 숫자가 포함된 리스트의 도식 표현. 숫자 15가 원으로 표시됩니다.

15 ???
리스트의 중간 요소와 search_value 비교

def binary_search(ordered_list, search_value):
  first = 0
  last = len(ordered_list) - 1

  while first <= last:
    middle = (first + last)//2
    if search_value == ordered_list[middle]:
      return True
    elif search_value < ordered_list[middle]:
      last = middle - 1
    else:
      first = middle + 1

  return False

이진 탐색 - 복잡도

복잡도: $O(\log{}n)$

선형 탐색과 이진 탐색의 그래프 표현.

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘