Click here to Skip to main content
15,748,330 members
Articles / General Programming / Algorithms
Posted 7 Feb 2023

Tagged as


4 bookmarked

An Alternative Rotated Binary Search

Rate me:
Please Sign up or sign in to vote.
4.00/5 (1 vote)
7 Feb 2023CPOL2 min read
A .NET7 version of a Rotated Binary Search method
In this tip, you will find a simplistic example of a Rotated Binary Search method in C#11.


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#.


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.


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}";
 Sample output
Mid Index = 5 split on value 11 key value  is 4

Mid Index = 8 split on value 2 key value  is 4

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}");


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.


  • 8th February, 2023: Initial version


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Written By
Wales Wales
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

Questionintro Pin
JohnDG529-Feb-23 3:06
JohnDG529-Feb-23 3:06 
AnswerRe: intro Pin
George Swan9-Feb-23 7:04
mveGeorge Swan9-Feb-23 7:04 

Thanks for your observation. I can see how the description could be confusing. I have updated the phraseology in the hope that it is more clear. Best wishes, George.

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.