(python)알고리즘, 자료구조 - 리스트의 2진탐색

오늘 배울 내용

• 선형탐색 vs 이진탐색
• 이진탐색의 방법
• 이진탐색 문제 및 풀이

선형탐색 : 리스트의 항목을 하나씩 살펴본다.

순서대로 하나씩 하나씩

이진탐색 : 처음과 끝의 중간값을 목표와 비교하며 찾는 범위를 줄여나간다.

이진법 문제

리스트 L 과, 그 안에서 찾으려 하는 원소 x 가 인자로 주어질 때, x 와 같은 값을 가지는 원소의 인덱스를 리턴하는 함수 solution() 을 완성하세요. 만약 리스트 L 안에 x 와 같은 값을 가지는 원소가 존재하지 않는 경우에는 -1 을 리턴합니다.

 

(가정)

• 리스트 L 은 자연수 원소들로 이루어져 있으며, 크기 순으로 정렬되어 있음
• 동일한 원소는 두 번 이상 나타나지 않음

나의 문제 풀이

def solution(L, x):
    answer = 0
    low = 0
    upp = len(L) - 1
    while low != upp:
        if upp-low == 1:
            break
        else:
            mid = int((low + upp)/2)
            if L[mid] < x:
                low = mid
            elif L[mid] > x:
                upp = mid
            elif L[mid] == x:
                answer = mid
                break
    if answer == 0:
        answer = -1
    return answer