• Region 1 contains all items having index value less than ind1

• Region 2 contains all items having index value greater than ind1 but less than ind2

• Region 3 contains all items having index value greater than ind2

If possible, the sizes of these regions should be equal. If this is not possible, then the size of Region 1 must be greater than or equal to the size of Region 2, and the size of Region 2 must be greater than or equal to the size of Region 3. The sizes of any two regions may differ by at most one.

The format I'm trying to follow is:

if the size of the search region is <= 4

perform a linear search for v

else

select indexes ind1 and ind2 if L[ind1] is equal to v

stop, we have found v else if v < L[ind1]

repeat with Region 1 being the new search region else if L[ind2] is equal to v

stop, we have found v else if v < L[ind2]

repeat with Region 2 being the new search region else

repeat with Region 3 being the new search region

Along with searching through the list, I also need to produce the steps as the algorithm checks.

For example:

ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,8 6,88,94], 88) should print:

Checking if 88 is equal to 38

Checking if 88 is less than 38

Checking if 88 is equal to 75

Checking if 88 is less than 75

Checking if 88 is equal to 81

Checking if 88 is less than 81

Checking if 88 is equal to 88

Search successful

88 is located at index 17

A total of 7 comparisons were made

The code I've written is:

def ternary_search(L,val): length = len(L) left = 0 right = length ind1 = length // 3 ind2 = (length - ind1) // 2 R1 = L[0:(ind1-1)] R2 = L[(ind1+1):(ind2-1)] R3 = L[(ind2+1):length] while True and R1 <= R2 and R2 <= R3: if left == right: # if the list is empty, produce [0] print("Search not successful") elif right <= 4: for val in L: print("Checking if " + str(val) + " is equal to " + str(L[0])) if val == L[0]: print("Search successful") print(str(val) + " is located at index 0") print("A total of 1 comparison was made") elif val != L[0]: print("Checking if " + str(val) + " is equal to " + str(L[1])) elif val == L[1]: print("Search successful") print(str(val) + " is located at index 1") print("A total of 2 comparisons were made") elif val != L[1]: print("Checking if " + str(val) + " is equal to " + str(L[2])) elif val == L[2]: print("Search successful") print(str(val) + " is located at index 2") print("A total of 3 comparisons were made") elif val != L[2]: print("Checking if " + str(val) + " is equal to " + str(L[3])) elif val == L[3]: print("Search successful") print(str(val) + " is located at index 3") print("A total of 4 comparisons were made") elif val != L[3]: print("Search not successful") print("A total of 4 comparisons were made") elif val == L[ind1]: print("Checking if " + str(val) + " is equal to " + str(ind1)) print("Search successful") print(str(val) + " is located at index 4") elif val < L[ind1]: print("Checking if " + str(val) + " is less than " + str(ind1)) length = len(R1) ind1 = length // 3 ind2 = (length - ind1) // 2 elif val == L[ind2]: print("Checking if " + str(val) + " is equal to " + str(ind2)) print("Search successful") print(str(val) + " is located at index " + str(ind2)) elif val < L[ind2]: print("Checking if " + str(val) + " is greater than " + str(ind1)) length = len(R2) ind1 = length // 3 ind2 = (length - ind1) // 2 else: length = len(R3) ind1 = length // 3 ind2 = (length - ind1) // 2