이진탐색

def binary_search(array,target,start,end):
    if start>end:
        return None
    mid=(start+end)//2 

    # 찾을 경우 중간점의 인덱스 반환
    if array[mid]==target:
        return mid
    # 중간 값이 찾는 값보다 큰 경우 왼쪽에서 탐색
    elif array[mid]>target:
        return binary_search(array,target,start,mid-1)
    # 중간 값이 찾는 값보다 작은 경우 오른쪽에서 탐색
    else:
        return binary_search(array,target,mid+1,end)

#원소 개수, target(찾고자 하는 문자) 입력
n,target=map(int,input().split())
#전체 원소
array=list(map(int,input().split()))

result=binary_search(array,target,0,n-1)
if result==None:
    print('원소가 존재하지 않습니다')
else:
    print(result+1)

def binary_search(array,target,start,end):
    while start<=end:
        mid=(start+end)//2

        if array[mid]==target:
            return mid
        # 중간 값이 찾는 값보다 큰 경우 왼쪽에서 탐색
        elif array[mid]>target:
            end=mid-1
        # 중간 값이 찾는 값보다 작은 경우 오른쪽에서 탐색
        else:
            start=mid+1
    return None

n,target=map(int,input().split())
array=list(map(int,input().split()))

result=binary_search(array,target,0,n-1)

if result==None:
    print("원소가 존재하지 않습니다")
else:
    print(result+1)

이진 탐색

• 배열 내부 데이터가 정렬돼야 사용가능
• 반으로 쪼개면서 탐색
• 시간 복잡도 O(logN)
• 자주 나오므로 코드 암기하는게 좋음