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;
using System.Threading.Tasks;
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;
}
}
}