[알고리즘] 간단한 이진탐색 구현

포인트

• 간단한 이진 탐색을 구현해보자
• 이진 탐색의 조건은? -> 정렬이 되어 있어야 한다.
• lower_bound, upper_bound 의 개념을 사용할 수 있다.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

python

def binarySearch(arr, target: int) -> int:
    left = 0
    right = len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2

        if mid == target:
            return target
        elif arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return -1

 

이진 탐색에서 mid 값을 left+(left-eight)//2 로 구한 이유는?

> 자칫 발생할 수 있는 오버플로우를 예방 하기 위해서 이다. 

left + (left-right)//2 == (left+right)//2 와 논리적으로 동일하지만 left+right 는 오버플로우가 발생할 수 있다. 따라서, 이것을 해결할 필요성이 있다.