An Alternative Rotated Binary Search

• Download source code - 2 KB

Background

This tip details a Rotated Binary Search method as an alternative to the examples illustrated in the excellent CodeProject article, Solutions to the Rotated Binary Search Problem in C#.

Introduction

A rotated binary search is a search carried out on a sorted array that has been split about a pivot point and reconstituted so that the sub array on the right of the point is placed behind the left sub array.

Int[] baseArray= {1, 2, 3, 4, 5, 6, 7 ,8 ,9, 10, 11, 12};
//split on  value 5
int[] rotatedArray = { 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5 };

An important characteristic of this type of array is that, wherever it is split, at least one side of the array will be sorted. This occurs because there is only one point of ascending discontinuity between adjacent numbers, in this example, it is between the values 12 and 1.

The Binary Search

The search is recursive. It eliminates half of the range under consideration on each recursive call. This is done by splitting on the mid index value of the range. If the value at the index is equal to the search key, the search is over, if not, it finds the side of the spit that is sorted and determines if the key exists within its range. If it does exist, that side is recursively searched, if not, the other side is recursively searched. An out of bounds condition arises when the low index of the range is greater than the high index and a -1, 'not found' value, is returned.

Implementation

The aim here is to keep the code as brief as possible and to avoid multiple if, then, else statements that tend to litter these sorts of algorithms.

int[] array = { 6, 7, 8, 9, 10, 11, 12, 1, 2, 3, 4, 5 };
//search for each value in the array
foreach (int n in array)
{
    int index = RotatedSearch(array, 0, array.Length - 1, n);
    string message = index > -1 ? $" Found Key {n} it is at array index {index}" :
        $" Failed to find Key {n}";
    Console.WriteLine(message);
}
Console.ReadLine();
/*
 Sample output
[6,7,8,9,10,11,12,1,2,3,4,5]
Mid Index = 5 split on value 11 key value  is 4

 [12,1,2,3,4,5]
Mid Index = 8 split on value 2 key value  is 4

 [3,4,5]
Mid Index = 10 split on value 4 key value  is 4
 Found Key 4 it is at array index 10
*/

static int RotatedSearch(int[] arr, int low, int high, int key)
{
    int pivot = (low + high) / 2;
    PrintArray(arr, low, high, pivot, key);
    if (low > high) return -1;          //out of bounds=> key not found
    if (arr[pivot] == key) return pivot;// key found
    //if left side is sorted and left side contains the key
    //OR if left side is not sorted and right side does not contain the key
    //search left ELSE search right
    return ((arr[low] <= arr[pivot]) && (arr[low] <= key && arr[pivot] > key)) ||
             arr[low] > arr[pivot] && !(key > arr[pivot] && key <= arr[high]) ?
             RotatedSearch(arr, low, pivot - 1, key) : 
             RotatedSearch(arr, pivot + 1, high, key);
}

static void PrintArray(int[] arr, int start, int end, int mid, int key)
{
    var range = arr.Where((n, i) => i >= start && i <= end);
    Console.WriteLine($"\r\n [{string.Join(',', range)}] ");
    Console.WriteLine($" Mid Index={mid} split 
                      on value {arr[mid]} key value  is {key}");
}

Conclusion

The example using the RotatedSearch and PrintArray methods is mainly of academic interest but I found it to be a useful exercise in the management of arrays in general and ranges in particular.

History

• 8^th February, 2023: Initial version