이진 탐색

탐색할 자료를 둘로 나누어서 데이터를 탐색하는 방법이다.

 

만들기

 

find_data=찾는 숫자

data_list= 데이터 리스트

 

1. 데이터가 1개인 경우

   1-1 if 데이터가 찾는 데이터일경우

         True

   1-2 else: 

         False

 2.데이터가 1개도 없을 경우

  False

 

data_list의 중간값을 시작으로 find_data와 비교해서

3-1 if data_list[middle]>find_data:

      맨앞부터 middle까지의 범위에서 다시 find_data찾기

3-2 elif data_list[middle]<find_data:

      middle에서 맨끝까지 다시 find_data찾기

3-3둘다 아니면 middle=find_data인경우.

 

시간 복잡도 

:n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산 k번 진행

O(logn)

 

def binary_search(data,search):
    print(data)
    #데이터가 1개밖에 없을 때
    if len(data)==1:
        if data[0]==search:
            return True
        else:
            return False
    #데이터가 1개도 없을 때
    if len(data)==0:
        return False
    #초기값= data_list의 중간값
    medium=len(data)//2

    if data[medium]==search:
        return True
    if data[medium]<search:
        return binary_search(data[medium:],search)
    else:
        return binary_search(data[:medium],search)

import  random
data_list=random.sample(range(100),11)
data_list.sort()
print( binary_search(data_list,50) )