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;
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] &lt;= 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 &lt; indexMin)  
            {
                return -1;
            }
            if (indexMax == indexMin)
            {
                return indexMin;
            }
            int mid = (indexMin + indexMax)/2;   /*low + (high - low)/2;*/
            if (mid &lt; indexMax &amp;&amp; array[mid] &gt; array[mid + 1])
            {
                return mid;
            }
            if (mid &gt; indexMin &amp;&amp; array[mid] &lt; array[mid - 1])
            {
                return (mid-1);
            }
            if (array[indexMin] &gt;= 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 &gt; indexMax)
            {
                return -1;
            }

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

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

        public int FindIndexIterative(int numberToFind, int[] array, int indexMin, int indexMax)
        {
            while (indexMin &lt; indexMax)
            {
                int mid = ((indexMax - indexMin) / 2) + indexMin;
                if (array[mid] &lt; numberToFind)
                {
                    indexMin = mid;
                }
                else if (numberToFind &lt; array[mid])
                {
                    indexMax = mid;
                }
                else 
                {
                    return mid;
                }
            }
            return -1;
        }
    }
}
If numberToFind &gt; 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] &lt; numberToFind. It seems more natural to me to perform the equivalent test numberToFind &gt; array[mid]:

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


mid can be found more easily with:

int mid = (indexMin + indexMax) / 2;