Binary Cut

Write a module containing a function which returns the position of a particular number in an array of sorted integers. The function should employ the so-called ``binary cut'' method. This method proceeds by determining in which half the number is and then concentrating on that half. It is easily implemented using two indices to point at the low and high positions of the current area of interest. It is assumed that if there is more than one occurrence of the number then the one with the higher index will be chosen. This method is very efficient for very large arrays.

Algorithm,

• Let i and j be the indices of the low and high marks.
• Initially set i = 1 and j = n (the number in the list)
• Assume k is the number we are trying to find
• DO
  • IF( )EXIT
  • determine the half way point
  • IF k is above put
  • Otherwise put
• END DO
• j will now point at the number k

Go back to Notes

• Solution