Solutions to the Rotated Binary Search Problem in C#

• Download source code - 3.5 KB
• Download output text - 4.2 KB

Introduction

Search algorithms deal with the task of finding a value within a data structure, the most common being an array. Given a sorted array of length n, the simplest algorithm is sequential search which has an execution time of O( n ) in the worst case. Binary search is a good alternative to sequential search because its execution time is guaranteed to be O( log2 n ) in the worst case. A variation on binary search is the problem of conducting the search on a sorted array whose elements have been rotated an arbitrary number of positions. For example, consider the following array:

[ 6 7 8 9 10 11 12 1 2 3 4 5 ]

The 0-based position of number 3 is 9, while number 25 does not occur in the array. This is an example of the rotated binary search problem. This problem is sometimes posed in interviews as “shifted binary search” but it should be clear that, starting with a sorted array.

[ 1 2 3 4 5 6 7 8 9 10 11 12 ]

Its elements have been rotated, not shifted, to the right 7 positions. Recall that in any assembly language, rotations preserve all information, while shifts do not.

All the code described in this article will be assumed to reside within the namespace of a Visual Studio C# console application named RotatedBinarySearch. The complete code is in the attached ZIP file.

Recursive Solution

Rotated binary search is similar to ordinary binary search but with an important difference. A rotation of a sorted array partitions the array into a left segment and a right segment. In the rotated-array example above, the left segment spans the elements [ 6, 7, 8, 9, 10, 11, 12 ] and the right segment spans the elements [ 1, 2, 3, 4, 5 ]. So the task of rotated binary search is to determine in which segment binary search should be performed. Suppose that it is desired to find the position of number 5. The computation pattern should be something like the following:

Search for 5

RotatedBinSearch [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

RotatedBinSearch [ 12 1 2 3 4 5 ]

        BinarySearch [ 3 4 5 ]

        BinarySearch [ 5 ]

Position of 5 in a1: 11

The occurrence of 12 in the array argument to the recursive call to RotatedBinSearch is due to the computation of the mid point and, as can be seen, does not affect the result. With these considerations in mind, the recursive implementation of rotated binary search is as follows:

/// <summary>Recursively find a target in a sorted array that has been rotated
///          an arbitrary number of places.
/// </summary>
/// <param name="rotatedArray">Sorted array.</param>
/// <param name="start">Start index for the search.</param>
/// <param name="end">End index for the search.</param>
/// <param name="target">Value sought.</param>
/// <notes>
///        The elements of {rotatedArray} are spanned by indices {start} and {end}.
///
///        On the initial call, the value of {end} MUST be the index of the LAST
///        element of {rotatedArray}.
/// </notes>
/// <returns>The position of {target} in {rotatedArray} if it exists.
///          Otherwise, -1.
/// </returns>
static int RotatedBinSearch( int[] rotatedArray, int start, int end, int target )
{
   PrintArray( "RotatedBinSearch", rotatedArray, start, end );
   
   if ( start == end && rotatedArray[ start ] != target ) // {start} meets {end}.
   {
      return -1; // Not found.
   }
   
   int mid = start + ( end - start ) / 2;
   
   if( target == rotatedArray[ mid ] )
   {
      return mid;
   } 
   else if ( rotatedArray[ mid ] < rotatedArray[ start ] ) // Right half is 
                                                           // sorted linearly.
   { 
      if ( ( target > rotatedArray[ mid] ) && ( target <= rotatedArray[ end ] ) ) 
      {
         return BinarySearch( rotatedArray, mid + 1, end, target );
      } 
      else 
      {
         return RotatedBinSearch( rotatedArray, start, mid - 1, target );
      }
   } 
   else // Left half is sorted linearly.
   { 
      if ( ( target >= rotatedArray[ start ] ) && ( target < rotatedArray[ mid ] ) ) 
      {
         return BinarySearch( rotatedArray, start, mid - 1, target );
      } 
      else 
      {
         return RotatedBinSearch( rotatedArray, mid + 1, end, target );
      }
   }
}// RotatedBinSearch

/// <summary>Ordinary binary search over a segment of an array. 
/// </summary>
/// <param name="rotatedArray">Array on which to conduct the search.</param>
/// <param name="start">Start index for the search.</param>
/// <param name="end">End index for the search.</param>
/// <param name="target">Value sought.</param>
/// <notes>{rotatedArray} is sorted linearly, that is, 
///
///           rotatedArray[ start ] is less than or equal to rotatedArray[ end ].
/// </notes>
/// <returns>The position of {target} in {rotatedArray} if it exists.
///          Otherwise, -1.
/// </returns>
static int BinarySearch( int[] rotatedArray, int start, int end, int target )
{
   PrintArray( "\tBinarySearch", rotatedArray, start, end );
   
   if ( start == end && rotatedArray[ start ] != target ) // Not found
   {
      return -1;
   }
   
   int mid = start + ( end - start ) / 2;
   
   if ( target == rotatedArray[ mid ] )
   {
      return mid;
   } 
   else if ( target > rotatedArray[ mid ] ) 
   {
      return BinarySearch( rotatedArray, mid + 1, end, target );
   } 
   else // target < rotatedArray[ mid ]
   {
      return BinarySearch( rotatedArray, start, mid - 1, target );
   }
}// BinarySearch 

The two functions are declared as static because they are within a static class of a console application. Function PrintArray simply displays some text and an array. Again, the complete code is in the attached ZIP file.

Tail Recursion

A function is said to be tail recursive if no computation, other than return, is performed after a recursive call. Ironically, a counterexample is a good way to introduce tail recursion. The well known sorting algorithm MergeSort, which can be implemented recursively as follows, is not tail recursive.

/// <summary>Sort a segment of an array. 
/// </summary>
/// <param name="a">Source array.</param>
/// <param name="lb">Lower bound of the segment.</param>
/// <param name="ub">Upper bound of the segment.
/// </param>
static void MergeSort( int[] a, int lb, int ub )
{
    // 0 <= lb <= a.Length && 0 <= ub <= a.Length

    int m;

    if ( lb < ub - 1 )
    {
        m = ( lb + ub ) >> 1;
        MergeSort( a, lb, m ); // a[ lb .. m-1 ] is sorted
        MergeSort( a, m, ub ); // a[ m .. ub-1 ] is sorted
        MergeHalves( a, lb, m, ub );
    }
}// MergeSort

The gist of the algorithm is to partition the array to be sorted into two halves, recursively sort each half, and then merge (i.e., combine) the sorted halves. The code is not tail recursive because the first recursive call is followed by the second recursive call, which is followed by the merging process implemented as follows. The code is pretty much self-explanatory, and will not be discussed.

/// <summary>Merge the sorted left and right halves of an array. 
/// </summary>
/// <param name="a">Source array.</param>
/// <param name="lb">Lower bound of left half.</param>
/// <param name="m">Midpoint: 
///                 upper bound of left half and lower bound of right half.
/// </param>
/// <param name="ub">Upper bound of right half.
/// </param>
static void MergeHalves( int[] a, int lb, int m, int ub )
{
   int[] b = new int[ ub - lb ];
   int i, j, k;
   
   i = lb; j = m; k = 0;
   
   while ( i < m && j < ub )
   {
      if ( a[ i ] < a[ j ] )
      {
         b[ k++ ] = a[ i++ ];
      }
      else // a[ i ] >= a[ j ]
      {
         b[ k++ ] = a[ j++ ];
      }
   }
   // i == m || j == ub
   
   while ( i < m )
   {
      b[ k++ ] = a[ i++ ];
   }
   // i == m
   
   while ( j < ub )
   {
      b[ k++ ] = a[ j++ ];
   }
   // j == ub && k == ub - lb
   
   while ( 0 < k )
   {
      a[ --j ] = b[ --k ];
   }
}// MergeHalves 

Tail recursion can be removed from a function by replacing it with code to alter the function’s arguments according to the recursive call and transferring control to the beginning of the function, as will be shown next.

Iterative Solution

Rather than re-inventing the wheel in order to figure out the implementation of an iterative version of rotated binary search, observe that the two functions in the recursive solution indeed are tail recursive. So, if the recursive calls are replaced by equivalent code, the iterative solution is a by-product of the recursive one. The following two functions implement the iterative solution.

/// <summary>Iteratively find a target in a sorted array that has been rotated
///          an arbitrary number of places.
/// </summary>
/// <param name="rotatedArray">Sorted array.</param>
/// <param name="start">Start index for the search.</param>
/// <param name="end">End index for the search.</param>
/// <param name="target">Value sought.</param>
/// <notes>
///        The elements of {rotatedArray} are spanned by indices {start} and {end}.
///
///        On the initial call, the value of {end} MUST be the index of the LAST
///        element of {rotatedArray}.
/// </notes>
/// <returns>The position of {target} in {rotatedArray} if it exists.
///          Otherwise, -1.
/// </returns>
static int IterRotBinSearch( int[] rotatedArray, int start, int end, int target )
{
   PrintArray( "IterRotBinSearch", rotatedArray, start, end );
   
L0: // Label to jump to when tail-recursion is removed.

   if ( start == end && rotatedArray[ start ] != target ) // {start} meets {end}.
   {
      return -1; // Not found.
   }
   
   int mid = start + ( end - start ) / 2;
   
   if( target == rotatedArray[ mid ] )
   {
      return mid;
   } 
   else if ( rotatedArray[ mid ] < rotatedArray[ start ] ) // Right half is sorted 
                                                           // linearly.
   { 
      if ( ( target > rotatedArray[ mid] ) && ( target <= rotatedArray[ end ] ) ) 
      {
         return IterBinSearch( rotatedArray, mid + 1, end, target );
      } 
      else 
      {
         // Removal of tail-recursive call in recursive solution:
         //
         //    return RotatedBinSearch( rotatedArray, start, mid - 1, target );
         
         end = mid - 1;
         goto L0;
      }
   } 
   else // Left half is sorted linearly.
   { 
      if ( ( target >= rotatedArray[ start ] ) && ( target < rotatedArray[ mid ] ) ) 
      {
         return IterBinSearch( rotatedArray, start, mid - 1, target );
      } 
      else 
      {
         // Removal of tail-recursive call in recursive solution:
         //
         //    return RotatedBinSearch( rotatedArray, mid + 1, end, target );
         
         start = mid + 1;
         goto L0;
      }
   }
}// IterRotBinSearch

/// <summary>Iterative binary search over a segment of an array. 
/// </summary>
/// <param name="rotatedArray">Array on which to conduct the search.</param>
/// <param name="start">Start index for the search.</param>
/// <param name="end">End index for the search.</param>
/// <param name="target">Value sought.</param>
/// <notes>{rotatedArray} is sorted linearly, that is, 
///
///           rotatedArray[ start ] is less than or equal to rotatedArray[ end ].
/// </notes>
/// <returns>The position of {target} in {rotatedArray} if it exists.
///          Otherwise, -1.
/// </returns>
static int IterBinSearch( int[] rotatedArray, int start, int end, int target )
{
   PrintArray( "\tIterBinSearch", rotatedArray, start, end );
   
L0: // Label to jump to when tail-recursion is removed.

   if ( start == end && rotatedArray[ start ] != target ) // Not found
   {
      return -1;
   }
   
   int mid = start + ( end - start ) / 2;
   
   if ( target == rotatedArray[ mid ] )
   {
      return mid;
   } 
   else if ( target > rotatedArray[ mid ] ) 
   {
      // Removal of tail-recursive call in recursive solution:
      //
      //    return BinarySearch( rotatedArray, mid + 1, end, target );
      
      start = mid + 1;
      goto L0;
   } 
   else // target < rotatedArray[ mid ]
   {
      // Removal of tail-recursive call in recursive solution:
      //
      //    return BinarySearch( rotatedArray, start, mid - 1, target );
      
      end = mid - 1;
      goto L0;
   }
}// IterBinSearch 

On the Use of the goto Statement

A very long time ago, the late Edsger Dijkstra published a now classic paper titled “Go To Statement Considered Harmful” (Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148). In that paper, Dijkstra called for the abolishment of the goto statement from all “higher level” programming languages, warned against the unbridled use of it, and pointed out that it was “too much an invitation to make a mess of one’s program” (that is, to write what became known as “spaghetti code”).

Although the author completely agrees with his former teacher’s view, it must be observed that the use of the goto statement to remove tail recursion from the recursive solution to derive the iterative solution does not constitute an unbridled use of the statement but a controlled way to perform an equivalent iterative computation.

Array Rotations

For testing purposes, it is convenient to be able to rotate the elements of the array in which searches are to be conducted. Suppose that an n-element array a is to be rotated m positions, where m < n. A simple way to achieve the rotation involves a function like the following:

/// <summary>Simple algorithm to rotate the elements of an array. 
/// </summary>
/// <param name="a">Array whose elements are to be rotated.</param>
/// <param name="m">Number of rotation positions.</param>
/// <notes>
///        This algorithm works one element at a time.
///        Hence, it must run {m} times.
///        If {n} is the length of {a}, the time complexity
///           of the algorithm is O( n * m ).
/// </notes>
static void SimpleRotateRight( int[] a, int m )
{
   int n = a.Length;
   int b;
   
   PrintArray( "\n  Array: ", a );
   
   for ( int j = 0; j < m; ++j )
   {
      // Copy the first element to {b}.
      b = a[ 0 ];
      
      // Copy the last element to the first position.
      a[ 0 ] = a[ n - 1 ];
      
      // Shift right the next-to-last down to the first
      // elements by one position.
      for ( int i = n - 2; i > 0; --i )
      {
         a[ i + 1 ] = a[ i ];
      }
      
      // Store the temporary variable in the first
      // element position.
      a[ 1 ] = b;
   }
   Console.Write( "\nSimpleRotateRight {0} positions:\n", m );
   PrintArray( "Rotated: ", a );
}// SimpleRotateRight

This implementation does the job but is expensive for large arrays: it is not difficult to show that its execution time is O( mn ). A way to perform the rotation more efficiently is to handle “chunks” of elements the proper way. The following figure illustrates the efficient implementation of array rotation. The code is given, with suitable comments, after the figure:

/// <summary>Rotate right the elements of an array. 
/// </summary>
/// <param name="arr">Array whose elements are to be rotated.</param>
/// <param name="m">Number of positions to rotate.
/// </param>
static void RotateRight( int[] arr, int m )
{
   int n = arr.Length;
   
   if ( m > 0 && m < n )
   {
      int n_m = n - m;
      
      if ( n_m <= m )
      {
         RotationNotPossible( arr, n, m, n_m );
      }
      else
      {
         PrintArray( "\n  Array: ", arr );
         
         // Define an array {b} to hold copies of
         // elements arr[ 0 ] ... arr[ m - 1 ].
         
         int[] b = new int[ m ];
         int i, j;
         
         for ( i = 0; i < m; ++i )
         {
            b[ i ] = arr[ i ];
         }
         // i == m
         
         // Copy the elements arr[ n - m ] ... arr[ n - 1 ] 
         // to arr[ 0 ] ... arr[ m - 1 ].
         
         for ( i = 0, j = n_m; j < n; ++i, ++j )
         {
            arr[ i ] = arr[ j ];
         }
         // i == m && j == n
         
         // Copy the elements arr[ m ] ... arr[ n - m - 1 ] to the end of 
         // {arr} starting at {n - m - 1} and going backwards.
         
         for ( i = n - m - 1, j = n - 1; i >= m; --i, --j )
         {
            arr[ j ] = arr[ i ];
         }
         // i == m - 1
         
         // Copy the elements of array {b} backwards starting at arr[ j ].
         
         for ( i = m - 1; i >= 0; --i, --j )
         {
            arr[ j ] = b[ i ];
         }
         
         Console.Write( "\nRotateRight {0} positions:\n", m );
         PrintArray( "Rotated: ", arr );
      }
   }
}// RotateRight    

Although the implementation of function RotateRight certainly is more complicated than that of function SimpleRotateRight, its execution time is O( n ). Hence, it is more efficient.

As shown in the figure preceding the code, in function RotateRight, it is assumed that the array can be conceptually partitioned into three sections, the first and last having the same length. Let n be the length of the array and m be the number of positions to rotate right. If (n – m) <= m, there would not be three partitions, and the resulting array would not contain the correct result. To signal this situation, function RotationNotPossible is called.

/// <summary>Display a {MessageBox} indicating that an
///          array rotation is not possible.
/// </summary>
/// <param name="a">Array to be rotated.</param>
/// <param name="n">Length of array to be rotated.</param>
/// <param name="m">Number of rotate positions.</param>
/// <param name="n_m">{n} - {m}.
/// </param>
static void RotationNotPossible( int[] a, int n, int m, int n_m )
{
   StringBuilder sb = new StringBuilder();
   
   sb.Append( "RotateRight: Rotation not possible.\n" );
   sb.Append( ArrayToString( "Array {a}:", a ) );
   sb.Append( String.Format( "\nArray length: n == {0}\n", n ) );
   sb.Append( String.Format( "Rotate positions: m == {0}\n", m ) );
   sb.Append( String.Format( "n - m (== {0}) <= m (== {1})\n", n_m, m ) );
   sb.Append( "There would not be three partitions in the array:\n" );
   sb.Append( 
      String.Format( "a[ 0 ] .. a[ {0} ], a[ {1} ] .. a[ {2} ], a[ {3} ] .. a[ {4} ].",
                     m - 1, m, n_m - 1, n_m, n - 1 ) );
                     
   string sbStr = sb.ToString();
   
   MessageBox.Show( sbStr );
   Console.WriteLine( "\n" + sbStr );
}// RotationNotPossible  

This function generates an appropriate error message, displays it in a MessageBox and, after the user clicks on the OK button, echoes the message on the command prompt window.

Driver Test Function

To test the recursive and iterative implementations of rotated binary search, and to verify that they produce the same result, it is a simple matter to write a driver function.

/// <summary>Driver function for rotated binary search. 
/// </summary>
/// <param name="name">Array name.</param>
/// <param name="rotatedArray">Array on which searches are to be performed.</param>
/// <param name="target">Value to search for.
/// </param>
static void FindInArray( string name, int[] rotatedArray, int target )
{
   int n_1 = rotatedArray.Length - 1, index;
   
   SearchLegend( target );
   
   index = RotatedBinSearch( rotatedArray, 0, n_1, target );
   PrintResult( target, index, name );
   
   index = IterRotBinSearch( rotatedArray, 0, n_1, target );
   PrintResult( target, index, name );
}// FindInArray 

When this function is called with the previous search example, the full computation pattern is as follows:

Search for 5

RotatedBinSearch [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

RotatedBinSearch [ 12 1 2 3 4 5 ]

        BinarySearch [ 3 4 5 ]

        BinarySearch [ 5 ]

Position of 5 in a1: 11

IterRotBinSearch [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

        IterBinSearch [ 3 4 5 ]

Position of 5 in a1: 11

Function SearchLegend just displays a message about the search.

Main Program

With all the previous functionality in place, the Main program can conduct several test searches and rotations.

static void Main( string[] args )
{
   int[] a1 = { 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5 },
         a2 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 },
         a3 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
         
   PrintArray( "Array a1:", a1, 0, 11 );
   
   // Positive: target = 3, target = 8.
   
   FindInArray( "a1", a1, 3 ); // Should be 9.
   FindInArray( "a1", a1, 8 ); // Should be 2.
   
   // Negative: target = 0, target = 13.
   
   FindInArray( "a1", a1, 0 );  // Should fail.
   FindInArray( "a1", a1, 13 ); // Should fail.
   
   // Boundary: target = 6, target = 5.
   
   FindInArray( "a1", a1, 6 ); // Should be 0.
   FindInArray( "a1", a1, 5 ); // Should be 11.
   
   RotateRight( a1, 3 );
   
   FindInArray( "a1", a1, 5 ); // Should be 2.
   
   // Tests on function {RotateRight}.
   
   RotateRight( a2, 7 ); // Should generate error message.
   RotateRight( a2, 4 ); // Should work.
   RotateRight( a2, 3 ); // Should work.
   
   SimpleRotateRight( a3, 7 );
   
   Console.WriteLine();
}// Main 

The output from the program is a bit long and will not be reproduced in full here. Suffice it to say that the results in the output agree with what the comments indicate. However, a few interesting cases demonstrate the program’s execution.

The output from the second negative-result case illustrates the sequence of attempts by function RotatedBinSearch to find a segment in the array to perform binary search.

Search for 13

RotatedBinSearch [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

RotatedBinSearch [ 12 1 2 3 4 5 ]

RotatedBinSearch [ 12 1 ]

RotatedBinSearch [ 1 ]

13 does not occur in a1

IterRotBinSearch [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

13 does not occur in a1

The output from the second boundary case is as follows:

Search for 5

RotatedBinSearch [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

RotatedBinSearch [ 12 1 2 3 4 5 ]

        BinarySearch [ 3 4 5 ]

        BinarySearch [ 5 ]

Position of 5 in a1: 11

IterRotBinSearch [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

        IterBinSearch [ 3 4 5 ]

Position of 5 in a1: 11

The call to function RotateRight and the subsequent call to function FindInArray produce the following output:

Array:  [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

RotateRight 3 positions:

Rotated:  [ 3 4 5 6 7 8 9 10 11 12 1 2 ]

Search for 5

RotatedBinSearch [ 3 4 5 6 7 8 9 10 11 12 1 2 ]

        BinarySearch [ 3 4 5 6 7 ]

Position of 5 in a1: 2

IterRotBinSearch [ 3 4 5 6 7 8 9 10 11 12 1 2 ]

        IterBinSearch [ 3 4 5 6 7 ]

Position of 5 in a1: 2

The last three calls to RotateRight are further tests on the function. If array a2 were rotated 7 positions, the result would be equivalent to array a1. The call RotateRight( a2, 7 ) causes the display of the following MessageBox, with the same message printed in the command prompt window.

The last two calls to RotateRight are one possible way to achieve the intended result, as shown by the output produced.

  Array:  [ 1 2 3 4 5 6 7 8 9 10 11 12 ]

RotateRight 4 positions:

Rotated:  [ 9 10 11 12 1 2 3 4 5 6 7 8 ]

  Array:  [ 9 10 11 12 1 2 3 4 5 6 7 8 ]

RotateRight 3 positions:

Rotated:  [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

(This is reminiscent of Eddie Izzard’s joke, in “LIVE from Wembley”, of a man who could count only up to three, and who apparently did not know plurals: to order five beers he would say “three beer, two beer”. End of joke.)

Just for completeness, the Main program calls function SimpleRotateRight to rotate array a3 by 7 positions. The resulting array should be equivalent to array a1, which indeed is the case.

Array:  [ 1 2 3 4 5 6 7 8 9 10 11 12 ]

SimpleRotateRight 7 positions:

Rotated:  [ 6 7 8 9 10 11 12 1 2 3 4 5 ]

Using the Code

To use the code, create a Visual Studio C# console application with the name RotatedBinarySearch. Replace the generated code in file Program.cs with the contents of file Program.cs included in the ZIP file. Add a reference to the System.Windows.Forms DLL as follows. In the Solution Explorer pane, right-click on References. In the list that appears, click on Add Reference. In the window that appears, click on the .NET tab, scroll down to the entry System.Windows.Forms and click on it. Build the application and run it without debugging. The output shown in the command prompt window should be identical to the contents of file out.txt included in the ZIP file.

History

• 1^st February, 2023: Initial version