15,748,330 members
Articles / General Programming / Algorithms
Tip/Trick
Posted 7 Feb 2023

5.8K views
4 bookmarked

# An Alternative Rotated Binary Search

Rate me:
4.00/5 (1 vote)
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.

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

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

C#
```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);
}
/*
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

• 8th February, 2023: Initial version

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