In this tip, you will find a simplistic example of a Rotated Binary Search method in C#11.

## 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};
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 };
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();
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;
if (arr[pivot] == key) return pivot;
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

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