В моем алгоритме бинарного поиска Python не находит 0 проиндексированных членов в списке - PullRequest
Новая
       4

В моем алгоритме бинарного поиска Python не находит 0 проиндексированных членов в списке

2 голосов
/ 10 января 2020

Как я могу исправить код - алгоритм находит искомый номер для всех случаев, кроме случаев, когда вы пытаетесь найти 0 индексированное число или в моем случае search_num = 1. 

list1 = [1, 3, 4, 5, 19, 21, 52, 100, 152]
search_num = 1

def binarySearch(array, number):

    lower_b_index = 0
    upper_b_index = len(array) - 1

    while lower_b_index <= upper_b_index:

        mid_point = (lower_b_index + upper_b_index) // 2

        if array[mid_point] == number:
            return mid_point
        elif array[lower_b_index] == number:
            return lower_b_index
        else:
            if array[mid_point] < number:
                lower_b_index = mid_point + 1
            else: 
                upper_b_index = mid_point - 1 

    return False

a1 = binarySearch(list1, search_num)

if a1:
    print("The searched position: ", a1 + 1)
else:
    print("Not Found!")

1 Ответ

2 голосов
/ 10 января 2020

Ваша проблема не в вашем binarySearch al go, это ваше if заявление после.

Вы все go вернете a1 = 0, что правильно, и ваша проверка if 0 и 0 - логическое значение False

Простое исправление - return None и проверка if a1 is not None

list1 = [1, 3, 4, 5, 19, 21, 52, 100, 152]
search_num = 1

def binarySearch(array, number):

    lower_b_index = 0
    upper_b_index = len(array) - 1

    while lower_b_index <= upper_b_index:

        mid_point = (lower_b_index + upper_b_index) // 2

        if array[mid_point] == number:
            return mid_point
        elif array[lower_b_index] == number:
            return lower_b_index
        else:
            if array[mid_point] < number:
                lower_b_index = mid_point + 1
            else: 
                upper_b_index = mid_point - 1 

    return None  # Change here

a1 = binarySearch(list1, search_num)

if a1 is not None:  # Change here
    print("The searched position: ", a1 + 1)
else:
    print("Not Found!")
...