1
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.