7. 순차 탐색과 이진탐색

#1. 순차탐색(Sequential Search)**
* 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미
* 순차 탐색 : 데이터가 담겨 있는 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법
* 최악의 경우 리스트 길이가 n일떄 n번 비교해야함


from random import randint
data_list = list()
for num in range(10):
    data_list.append(randint(1, 100))
data_list

-->
[92, 66, 32, 49, 50, 12, 58, 58, 88, 87]


def sequencial(data_list, search_data):
  for index in range(len(data_list)):
    if data_list[index] == search_data:
      return index
    return -1
    
sequencial(data_list, 10) #찾으면 index, 찾지 못하면 -1
-->
-1


# 2. 이진 탐색(Binary Search)**
* 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

#2-1. 분할 정복 알고리즘과 이진 탐색
* 분할 정복 알고리즘
  * 문제를 하나 또는 둘 이상으로 나눔
  * 나눠진 문제가 충분히 적고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눔
* 이진탐색
  * 리스트를 두개의 서브 리스트로 나눔
  * 검색할 숫자가 중간값보다 작으면 앞부분의 서브 리스트에서 검색할 숫자를 찾음
  * 검색할 숫자가 중간값보다 크면 뒷부분의 서브 리스트에서 검색할 숫자를 찾음
  
  
  ##2-2 알고리즘 구현하기
* 이진 탐색은 데이터가 정렬되어있는 상태에서 진행
* 데이터가 [2,3,8,12,20]일때
  * binary_search(data_list, find_data) 함수를 만듦
  * data_list :데이터가 담긴 리스트
  * find_data : 찾는숫자
  * data_list의 중간값을 find data와 비교해서
    * find_data가 data_list의 중간값 보다 작다면, 맨앞부터 data_list의 중간값까지에서 find_data를 찾기
    * find_data가 data_list의 중간값보다 크다면, data_list의 중간부터 맨끝까지 find_data를 찾기
    * 그렇지 않다면 data_list의 중간값은 find_data인경우
    
    
def binary_search(data, search):
    print(data)
    if len(data) == 1 and search == data[0]:
        return True
    if len(data) == 1 and search != data[0]:
        return False
    if len(data) == 0:
        return False
    medium = len(data) // 2
    if search == data[medium]:
        return True
    else:
        if search > data[medium]:
            return binary_search(data[medium+1:], search)
        else:
            return binary_search(data[:medium], search)    


import random
data_list = random.sample(range(100), 10)
data_list
-->
[38, 82, 95, 41, 89, 11, 18, 40, 65, 58]


data_list.sort()
data_list
-->
[11, 18, 38, 40, 41, 58, 65, 82, 89, 95]


binary_search(data_list, 60)
-->
[11, 18, 38, 40, 41, 58, 65, 82, 89, 95]
[65, 82, 89, 95]
[65, 82]
[65]
False