[이분탐색] - 프로그래머스 고득점 kit

오름차순으로 정렬된 배열에서 원하는 숫자를 찾는 알고리즘이다.

 

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

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

left 와 right 변수를 초기화 해준다. left 가 right 보다 작을 때 까지 반복을 해준다.

 

mid 는 left 와 right 의 중간값이고, mid 가 target 보다 크면 왼쪽에 치우쳐 있다는 얘기니, right 값을 mid-1 로 줄여준다.

그렇지 않으면 오른쪽으로 치우쳐 있다는 것이니 left 를 mid+1 로 늘린다.

 

target 값과 일치할 때 까지 반복한다.