이진탐색

이진탐색

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
  • 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야함.
• 검색 과정
  • 자료의 중앙에 있는 원소를 고른다.
  • 중앙 원소의 값과 찾고자하는 목표값을 비교한다.
  • 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.

def binary_search(lst,target) :
    length = len(lst)
    start = 0
    end = lenght-1 #끝 쪽수
    while start<=end : #찾으려는 부분 처음이 끝보다 작거나 같으면
        middle = (start+end)//2 #middle start+end를 2로 나눈 값의 몫
        if target == lst[middle] : #target과 middle이 같으면
            return cnt #반복 횟수 반환
        elif lst[middle] > target : #middle이 찾으려는 target보다 크면
            end = middle-1 #마지막 부분 -1을 middle로 갱신
        else : #middle이 찾으려는 target보다 작으면
             start = middle+1 #처음 부분 +1을 middle로 갱신
    return False

1. 시작점과 끝점을 지정한다.
2. 시작점이 끝점보다 작거나 같으면
3. 중앙은 (시작점+끝점)을 2로 나눈 몫
4. 찾으려는 값과 일치하면
   1. 끝냄
5. 일치하지 않고 중앙값이 찾으려는 값보다 크면
   1. 끝점을 middle-1
6. 중앙값이 찾으려는 값보다 작으면
   1. 시작점을 middle+1로

• 재귀함수 이용

def binarySearch2(a,low,high,key) :
    if low>high :
        return False 
    else :
        middle = (low+high)//2
        if key == a[middle] : 
            return True
        elif key < a[middle] :
            return binarySearch2(a,low,middle-1,key)
        elif a[middle]<key :
            return binarySearch2(a,middle+1,high,key)

실제 문제에 적용

target = 25
m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(m_list)

m_list.sort()
left = 0
right = length-1

while left<=right:
    mid = (left+right)//2
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid]>target:
        right = mid-1
    else :
        left = mid+1


#이진탐색기 만들기
def binary_search(target) :
    start = 1 #책의 시작 쪽수
    end = Page #끝 쪽수
    cnt = 1 #반복 횟수
    while start<=end : #찾으려는 부분 처음이 끝보다 작거나 같으면
        middle = (start+end)//2 #middle start+end를 2로 나눈 값의 몫
        if target == middle : #target과 middle이 같으면
            return cnt #반복 횟수 반환
        elif middle > target : #middle이 찾으려는 target보다 크면
            end = middle #마지막 부분을 middle로 갱신
        else : #middle이 찾으려는 target보다 작으면
             start = middle #처음 부분을 middle로 갱신
        cnt +=1
    return False