Question

How to implement ternary search to find a value in a sorted list with Python

Answer 1

def ternary_search(l, r, key, lst):
    while l <= r:
        mid1 = l + (r - l) // 3
        mid2 = r - (r - l) // 3

        if lst[mid1] == key:
            return mid1
        if lst[mid2] == key:
            return mid2

        if key < lst[mid1]:
            r = mid1 - 1
        elif key > lst[mid2]:
            l = mid2 + 1
        else:
            l = mid1 + 1
            r = mid2 - 1

    return -1  # not found


def main():
    lst = [1, 2, 8, 14, 15, 64, 78, 89, 99, 100, 110, 123]
    to_search = 89

    index = ternary_search(0, len(lst) - 1, to_search, lst)

    if index != -1:
        print(f"Element found at index: {index}")
    else:
        print("Element not found.")


if __name__ == "__main__":
    main()



'''
run:

Element found at index: 7

'''

 

70+ SQL courses for beginners and professionals