이진 탐색 ( Binary Search )

■ 이진 탐색

1) 정의 :

1. 배열 전체의 중간값을 target 값과 비교
2. 중간값이 target 값보다 크면 왼쪽 부분만 선택
3. 왼쪽부분의 중간값을 다시 target 과 비교

 

■ 코드 구현

> plain 절차지향

def binary_search(m_list, target):
    
    m_list.sort()
    left = 0 
    right = len(m_list)-1

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

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

print(binary_search(m_list, target))

 

> 재귀

def binarySearch(array, target):
	
    left = 0
    right = len(array) - 1
    
    // sorting
    array.sort()
	
    middle_idx = (left+right)//2

    middle = array[middle_idx]
    print(f'middle : {middle}')
    if target == middle:
        return True
    elif middle > target:
        return binarySearch(array[:middle_idx], target)
    elif middle < target:
        return binarySearch(array[middle_idx+1:], target)
    else: 
        return False

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


print(binarySearch(m_list,target))

 

---

참조 :

velog.io/@madfinger/Binary-Search%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8C%8C%EC%9D%B4%EC%8D%AC

Binary Search(이진 탐색) - 파이썬