이진 탐색

Binary search
탐색범위를 반으로 줄여나가는 알고리즘
탐색 범위의 시작과 끝을 보관하는 변수를 사용

내 답안

• 힌트1의 시작, 끝 변수까지만 참고함
• '/': floating-point division
• '//': integer division
• 처음에는 대소 비교 후 first, end 변수를 그대로 넣어 줌. 테스트시 마지막이 None을 리턴해서 문제 발견. 즉 내 답안은 불완전함

-element가 중간값보다 작으면, 오른쪽 반은 더 이상 볼 필요가 없다.
element가 중간값보다 크면, 왼쪽 반은 더 이상 볼 필요가 없다.

def binary_search(element, some_list):
    first = 0
    end = len(some_list) - 1
   
   for item in range(len(some_list)):
        mid_index = (first + end) // 2
        if some_list[mid_index] == element:
            return mid_index
        else:
            if some_list[mid_index] > element:
                end = mid_index
            elif some_list[mid_index] < element:
                if some_list[mid_index + 1] == element:
                    return mid_index + 1
                else:
                    first = mid_index
    return None


print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

해답

• 반복문은 조건이 만족할 때까지만 반복하는 while 사용
• +1, -1 을 해주는 이유
  이진탐색은 예를 들어 1부터 50까지 들어있는 리스트가 있다고 해볼게용
  여기서 31을 찾고 싶다고 했을 때 중간값을 확인해봅니다.
  그런데 25는 31보다 작으니 1부터 25까지는 다시 확인을 하지 않아도 됩니다.
  그럼 탐색 범위가 26부터 50까지로 줄어들게 되겠죵.
  26부터 50까지 탐색하기 위해서 중간값에다가 1을 더해주면 됩니다.

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1
    
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
            return midpoint
        elif some_list[midpoint] > element:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

다른 사람 답변

def binary_search(element, some_list):
    index = len(some_list)//2
    
    for i in range(len(some_list)):
        if some_list[index] == element:
            return index
        elif some_list[index] > element:
            index = index//2
        elif some_list[index] < element:
            index = (index + len(some_list))//2
    return None