JMCanning78 / DemoRepo

0 stars 0 forks source link

Implement binary search of OrderedArray visualization #19

Open JMCanning78 opened 4 years ago

JMCanning78 commented 4 years ago

Implement the Search button and binary search algorithm visualization within the the OrderedArray VisualizationApp. This algorithm will also be called by the Insert and Delete operations. Here's the code for the binary search algorithm:

   def find(self, item):            # Find index at or just below
      lo = 0                        # item in ordered list
      hi = self.__nItems-1          # Look between lo and hi

      while lo <= hi:
         mid = (lo + hi) // 2       # Select the midpoint

         if self.__a[mid] == item:  # Did we find it at midpoint?
            return mid              # Return location of item

         elif self.__a[mid] < item: # Is item in upper half?
            lo = mid + 1            # Yes, raise the lo boundary

         else: 
            hi = mid - 1            # No, but could be in lower half

      return lo   # Item not found, return insertion point instead   

The other operations on the array are in separate issues.

JMCanning78 commented 4 years ago

This issue depends on issue: #18.