# Binary search using recursion, iteration, shifted array

Interview question some engineer, asked me to write binary search in 2 ways, Also asked me to write binary search on a shifted array (10 20 1 2 3 4). Wrote that and then asked me to find the offset of the array in log n.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
public class BinarySearch
{
public BinarySearch()
{
int[] array = new int[10] { 5, 6, 7, 8, 9, 10, 12, 15, 20, 30 };
int numberToFind = 10;
int index = FindIndexRecursive(numberToFind, array, 0, array.Length - 1);
Console.WriteLine("the number " + numberToFind + "is located at index: " + index);
index = FindIndexIterative(numberToFind, array, 0, array.Length - 1);
Console.WriteLine("the number " + numberToFind + "is located at index: " + index);
int[] shiftedArray = new int[6]{10, 20, 1, 2, 3 ,4};

index = FindShiftedArray(numberToFind, shiftedArray, 0, array.Length - 1);
}

private int FindShiftedArray(int numberToFind, int[] shiftedArray, int indexMin, int indexMax)
{
//we find the pivot and from there do a binary search
int pivot = FindPivot(shiftedArray, 0, shiftedArray.Length - 1);
//the pivot acts like the first slicing of the arrays
if (shiftedArray[pivot] == numberToFind)
return pivot;
if (shiftedArray[0] <= numberToFind)
{
return FindIndexRecursive(numberToFind,shiftedArray, 0, pivot - 1 );
}
else
{
return FindIndexRecursive(numberToFind,shiftedArray, pivot + 1, shiftedArray.Length - 1 );
}
}

private int FindPivot(int[] array, int indexMin, int indexMax)
{

if (indexMax < indexMin)
{
return -1;
}
if (indexMax == indexMin)
{
return indexMin;
}
int mid = (indexMin + indexMax)/2;   /*low + (high - low)/2;*/
if (mid < indexMax && array[mid] > array[mid + 1])
{
return mid;
}
if (mid > indexMin && array[mid] < array[mid - 1])
{
return (mid-1);
}
if (array[indexMin] >= array[mid])
{
return FindPivot(array, indexMin, mid-1);
}
else
{
return FindPivot(array, mid + 1, indexMax);
}
}

public int FindIndexRecursive(int numberToFind, int[] array, int indexMin, int indexMax)
{
if (indexMin > indexMax)
{
return -1;
}

int mid = ((indexMax - indexMin) / 2 ) + indexMin;

if (array[mid] < numberToFind)
{
return FindIndexRecursive(numberToFind, array, mid, indexMax);
}
else if (numberToFind < array[mid])
{
return FindIndexRecursive(numberToFind, array, indexMin, mid);
}
else
{
return mid;
}
}

public int FindIndexIterative(int numberToFind, int[] array, int indexMin, int indexMax)
{
while (indexMin < indexMax)
{
int mid = ((indexMax - indexMin) / 2) + indexMin;
if (array[mid] < numberToFind)
{
indexMin = mid;
}
else if (numberToFind < array[mid])
{
indexMax = mid;
}
else
{
return mid;
}
}
return -1;
}
}
}


If numberToFind > array[mid] then the lower bound should be set to mid + 1 as the value at array[mid] does not match. In the opposite case the upper bound should be set to mid - 1. If you don't do so, you might get stuck in an endless recursion. Say you are looking for 12 (at index 6) and you have indexMin = 5 and indexMax = 6. mid becomes 5. Now calling

FindIndexRecursive(numberToFind, array, mid, indexMax);


gives the same indexes again and array[mid] will never be 12!

I am also irritated by the test array[mid] < numberToFind. It seems more natural to me to perform the equivalent test numberToFind > array[mid]:

if (numberToFind > array[mid])
{
return FindIndexRecursive(numberToFind, array, mid + 1, indexMax);
}
else if (numberToFind < array[mid])
{
return FindIndexRecursive(numberToFind, array, indexMin, mid - 1);
}
else
{
return mid;
}


mid can be found more easily with:

int mid = (indexMin + indexMax) / 2;

• The last statement could cause an integer overflow for big enough indexMin and indexMax. OP's approach is safe. – Dmitry Dec 6 '14 at 0:13
• Good point. The limit, however, is at 2^31/2 = 1.07 billion items; high engough for most applications. – Olivier Jacot-Descombes Dec 6 '14 at 15:08