Python terminal search algorithm

Question

Python terminal search algorithm

I am trying to write a 3D search algorithm function that uses a sorted list of integers and a value. This is similar to binary search, except that the search area is divided into three smaller areas (having as short lengths as possible) at each iteration by choosing two indices ind1 and ind2 (ind1 <ind2):

• Region 1 contains all elements with index less than ind1

• Area 2 contains all elements with an index value greater than ind1 but less than ind2

• Area 3 contains all elements with an 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 should 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 size of any two regions may differ by no more than one.

The format I'm trying to follow is the following:

if the size of the search area is <= 4

do a linear search for v

yet

choose ind1 and ind2 if L [ind1] equals v

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

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

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

repeat with area 2 being the new search area

repeat with area 3 being the new search area

~~~~~

Along with searching the list, I also need to follow the steps to validate the algorithm.

~~~~~

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 be printed

Checking that 88 is 38

Check if 88 is less than 38

Checking that 88 is 75

Check if 88 is less than 75

Checking that 88 is 81

Checking that 88 is less than 81

Checking that 88 is 88

Search for successful

88 is at index 17

A total of 7 comparisons were made

~~~~~ The code I wrote:

    `def ternary_search (L, key):
        left = 0
        right = len(L) - 1
        while left <= right:
           ind1 = left
           ind2 = left + (right - left) // 3
           ind3 = left + 2 * (right - left) // 3
           n = 0

           if key == L[left]:
              n += 1
              print("Checking if " + str(key) + " is equal to " + str(left))
              print("Search successful")
              print(str(key) + " is located at index " + str(left))
              print("A total of " + str(n) + " comparisons were made")
              return

           elif key == L[right]:
              n += 1
              print("Checking if " + str(key) + " is equal to " + str(right))
              print("Search successful")
              print(str(key) + " is located at index " + str(right))
              print("A total of " + str(n) + " comparisons were made")
              return

           elif key < L[left] or key > L[right]:
              n += 1
              print("Search not successful")
              print("A total of " + str(n) + " comparisons were made")
              return

           elif key <= L[ind2]:
              n += 1
              print("Checking if " + str(key) + " is less than " + str(L[ind2]))
              right = ind2 -1

           elif key > L[ind2] and key <= L[ind3]:
              n += 1
              print("Checking if " + str(key) + " is less than " + str(L[ind2]))
              print("Checking if " + str(key) + " is equal to " + str(L[ind3]))
              print("Checking if " + str(key) + " is less than " + str(L[ind3]))         
              left = ind2 + 1
              right = ind3

           else:
              n += 1
              print("Checking if " + str(key) + " is less than " + str(L[ind3]))         
              left = ind3 + 1

        return`

When I call: ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94], 51)

It prints:

Checking if 51 is less than 38 Checking if 51 is equal to 73 Checking if 51 is less than 73 Checking if 51 is less than 51 Search not successful A total of 1 comparisons were made

When should it print:

Checking if 51 is equal to 38 Checking if 51 is less than 38 Checking if 51 is equal to 75 Checking if 51 is less than 75 Checking if 51 is equal to 53 Checking if 51 is less than 53 Checking if 51 is equal to 41 Checking if 51 is equal to 51 Search successful 51 is located at index 8 A total of 8 comparisons were made

+3

python algorithm time-complexity search ternary-search-tree

Shagun chhikara Jul 12 15 at 17:42

source to share

1 answer

user1952500 · Answer 1 · 2015-07-12T20:35:33+0000

Yes, you are correct that there was a lot wrong with the code above. Some of the things I found wrong were the following:

The list must be longer than the rightmost element.
The leftmost range will always start at 0 in your case.
Many unnecessary terms elif

, but I think it was only used for printing. In the meantime, there is no need to know about it. ”

The code should be very similar to binary search. An easier way to change what you described below. ( Edit: Fixed a few bugs in the code: the previous one wasn't exactly a triple search.)

def ternary_search (L, key):
   left = 0
   right = len(L) - 1
   while left <= right:
      ind1 = left
      ind2 = left + (right - left) // 3
      ind3 = left + 2 * (right - left) // 3
      if key == L[left]:
         print("Key found at:" + str(left))
         return
      elif key == L[right]:
         print("Key found at:", str(right))
         return
      elif key < L[left] or key > L[right]:
         print("Unable to find key")
         return
      elif key <= L[ind2]:
         right = ind2
      elif key > L[ind2] and key <= L[ind3]:
         left = ind2 + 1
         right = ind3
      else:
         left = ind3 + 1
   return

Test:

ternary_search([6,12,18,22,29,37,38,41,51,53,55,67,73,75,77,81,86,88,94],88)
('Key found at:', '17')

Note that it can be argued that binary search is the best in terms of comparisons between all n-ary searches.

Python terminal search algorithm

More articles: