pythonimportbinary-searchcustom-compare

I'm confused on what I am supposed to do and how I can do it


I am actually just confused on what this lab is asking for.

enter image description here:

The comparer looks like this (same thing for the numcomparer)

class StringComparer:
    def compare(self, string1, string2):
        if string1 < string2:
            return -1
        elif string1 > string2:
            return 1
        else:
            return 0

and the main file looks like this:
from Searcher import Searcher
from NumComparer import NumComparer
from StringComparer import StringComparer

def main():
    sorted_fruits = [
        "Apple", "Apricot", "Banana", "Blueberry", "Cherry",
        "Grape", "Grapefruit", "Guava", "Lemon", "Lime", "Orange",
        "Peach", "Pear", "Pineapple", "Raspberry", "Strawberry"
    ]
    fruit_searches = [
        "Nectarine", "Mango", "Guava", "Strawberry",
        "Kiwi", "Apple", "Raspberry", "Carrot", "Lemon", "Bread"
        ]
    expected_fruit_search_results = [-1, -1, 7, 15, -1, 0, 14, -1, 8, -1]

    string_comparer = StringComparer()
    print_searches(sorted_fruits,
                   fruit_searches,
                   string_comparer,
                   expected_fruit_search_results,
                   True);

    # Perform sample searches with integers
    integers = [11, 21, 27, 34, 42, 58, 66, 71, 72, 85, 88, 91, 98]
    integer_searches = [42, 23, 11, 19, 87, 98, 54, 66, 92, 1, 14, 21, 66, 87, 83]
    expected_integer_search_results = [4, -1, 0, -1, -1, 12, -1, 6, -1, -1, -1, 1, 6, -1, -1]

    num_comparer = NumComparer()
    print_searches(integers,
                   integer_searches,
                   num_comparer,
                   expected_integer_search_results,
                   False);

def print_searches(sorted_list,
                   search_keys,
                   comparer,
                   expected_results,
                   key_in_quotes):
    # If key_in_quotes is True, " characters surround the key in output
    # statements. Otherwise empty strings surround the key.
    extra = '\"' if key_in_quotes else ''

    for i in range(len(search_keys)):
        # Get the key to search for
        search_key = search_keys[i]

        # Peform the search
        index = Searcher.binary_search(sorted_list, search_key, comparer)

        # Compare actual result against expceted
        expected = expected_results[i]
        if index == expected:
            print(f"PASS: Search for key {extra}{search_key}{extra} returned {expected}.")
        else:
            print(f"FAIL: Search for key {extra}{search_key}{extra} should have returned {expected}, but returned {index}.")

if __name__ == '__main__':
    main()

I am unsure how to implement a binary search into this


Solution

  • I hope this helps you out 😊

    def binary_search(sorted_list, key, comparer):
            low = 0
            high = len(sorted_list) - 1
            while low <= high:
                mid = (low + high) // 2
                comparison_result = comparer.compare(sorted_list[mid], key)
                if comparison_result == 0:
                    return mid
                elif comparison_result <0:
                    low = mid + 1
                else:
                    high = mid - 1
            return -1