CH 12 Search

Search

Searching a List

• 내가 찾는 value의 index를 찾아 주는 함수
• linear search: index가 처음부터 끝까지 iteration을 돌며 값 비교

def linear_search(list, value):
   for i in range(len(list)):
      if (list[i] == value):
         return True
   return False

Binary Search

• list의 item들이 정렬되어 있을 때 사용하는 이진 탐색법
• list의 중간값을 업데이트하면서 value와 비교

def binary_search(list, value):
   start = 0
   end = len(list) - 1
   while (start <= end):
      mid = (start + end) / 2
      if (list[mid] > value):
         end = mid - 1
      elif (list[mid] < value):
         start = mid + 1
      else:
         return True
   return False