이진 탐색

이진탐색이란?

정렬된 데이터를 좌우 둘로 나눠서 원하는 값의 탐색범위를 좁혀가며 찾는 방법

 

-> 소주병 뚜껑 숫자맞출 때 쓰는 방법과 비슷하다. 

 

준비1

아래의 리스트서 중앙값을 찾으시오. 

a = [ 1, 7, 11, 12, 14, 23, 33, 47, 51, 64, 67, 77, 139, 672, 871 ]

import numpy as np

a = [ 1, 7, 11, 12, 14, 23, 33, 47, 51, 64, 67, 77, 139, 672, 871 ]

a = np.array(a)

print(np.median(a))

 

 

준비2

위 리스트에서 첫번째 숫자부터 중앙값에 해당하는 숫자까지만 검색하시오. 

a[:int(a.shape[0]/2+1)]

a[a<=47]

 

 

준비3

a 리스트에서 문제324번에서 선택되었던 숫자들을 중앙값까지 포함해서 다 지우고 아래의 결과만 출력하시오. 

[ 51 64 67 77 139 672 871]

a = a[int(a.shape[0]/2+1):]

print(a)

a = list(a)

del a[:a.index(np.median(a))+1]

print(a)

 

 

준비4

위의 a 리스트에서 중앙값을 출력하시오. 

a_m = np.median(a)

print(a_m)

 

 

준비5

아래의 a 리스트에 중앙값보다 작은 값만 남도록 아래의 결과 리스트만 출력되게 하시오. 

del a[a.index(a_m):]

print(a)

 

 

 

---

 

이진탐색 문제

이진탐색을 구현하시오.

import numpy as np

import math

 

# N개 랜덤수 생성&정렬

N = int(input('숫자의 개수를 입력하세요:'))

a = np.random.randint(1000, size=N)

a.sort(axis=0)

print(a)

 

< 방법 1 : while 문>

num = int(input('찾을 숫자를 입력하세요: '))

tryn = 1

 

# 리스트 길이가 0이 될때까지

while N!=0:

 

    # 중앙값일 경우

    if a[int(N/2)]==num:

        print(f'{num}이 리스트 내에 {tryn}회만에 검색됩니다.')

        break

 

    # 중앙값보다 작을 경우

    elif a[int(N/2)]>num:

        a = np.delete(a, np.s_[int((N+1)/2):])

        N -= int((N+1)/2)

 

    # 중앙값보다 클 경우

    else:

        a = np.delete(a, np.s_[:int((N+1)/2)])

        N -= int((N+1)/2)

    tryn+=1

 

# 이진탐색을 모두 했으나, 검색되지 않았을 경우

else:

    print(f'{num}이 리스트 내에 검색되지 않습니다.')

 

< 방법 2 : for 문, median 사용하지 않고>

num = int(input('찾을 숫자를 입력하세요: '))

a2 = a

 

# 0~log(2,N)회 탐색

for i in range(int(math.log(N, 2))+1):

    size = a2.shape[0]    # 중앙값을 찾기 위해 전체길이를 구해놓는다.

 

    # 중앙값일 경우

    if a2[int(size/2)]==num:

        print(f'{num}이 리스트 내에 {i+1}회만에 검색됩니다.')

        break

    

    # 중앙값보다 작을 경우

    elif a2[int(size/2)]>num:

        a2 = np.delete(a2, np.s_[int((size+1)/2):])

    

    # 중앙값보다 클 경우

    else:

        a2 = np.delete(a2, np.s_[:int((size+1)/2)])

 

# 이진탐색을 모두 했으나, 검색되지 않았을 경우

else:

    print(f'{num}이 리스트 내에 검색되지 않습니다.(시도횟수:{int(math.log(N, 2))+1})')

 

< 방법 3 : for 문, median 사용 >

num = int(input('찾을 숫자를 입력하세요: '))

a2 = a

 

# 0~log(2,N)회 탐색

for i in range(int(math.log(N, 2))+1):

    a_m=np.median(a2)

    

    # 중앙값일 경우

    if a_m==num:

        if a2[a2<=a_m][-1]==num:    # 전체길이가 짝수라 중앙값이 리스트내 존재하지 않을 경우를 방지하기 위해

            print(f'{num}이 리스트 내에 {i+1}회만에 검색됩니다.')

        else:

            print(f'{num}이 리스트 내에 검색되지 않습니다.(시도횟수:{i+1})')

        break   

    

    # 중앙값보다 작을 경우

    elif a_m>num:

        a2 = a2[a2<a_m]

 

    # 중앙값보다 클 경우

    else:

        a2 = a2[a2>a_m]

    

else:

    print(f'{num}이 리스트 내에 검색되지 않습니다.(시도횟수:{int(math.log(N, 2))+1})')