RelQ Software Company Limited Interview Question
Testing / Quality Assurancesa C version (return 0 if target is not found in arr):
int binary_search(int arr[], int init, int last, int target)
{
int intermidiate=init+floor(double(double(last-init)/double(2)));
if(last-init>0)
{
if(target==arr[intermidiate])
return intermidiate;
else
{
if(target<arr[intermidiate])
return binary_search(arr, init, intermidiate, target);
else
return binary_search(arr, intermidiate+1, last, target);
}
}
else if(last-init==0)
{
if (arr[last]==target)
return last;
else return 0;
}
else
return 0;
}
//C# Code
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace BinarySearch
{
class Program
{
static void Main(string[] args)
{
int[] array = new int[6] { -10, -2, 0, 4, 6, 10 };
int index = ReturnIndex(array, 6, 0, array.Length-1);
if (index == -1)
{
Console.WriteLine("Element not found");
}
else
{
Console.WriteLine("Located at position {0}", index);
}
Console.Read();
}
public static int ReturnIndex(int[] array, int num, int start, int end)
{
if (end < start)
{
return -1;
}
else
{
int mid = end - start / 2;
if (num > array[mid])
{
return ReturnIndex(array, num, mid + 1, end);
}
else if (num < array[mid])
{
return ReturnIndex(array, num, start, mid - 1);
}
else
{
return mid;
}
}
}
}
}
Output:
Located at position 4
#python version
- Mac February 28, 2010def search(arr,start,end,val):
retVal = (False,-1)
if ( start > end):
return retVal
mid = (start + end)/2
if ( val == arr[mid]):
retVal = (True,mid)
print "Found at %d"%mid
else:
if ( start == end):
print "Val %d does not exist "%val
elif ( arr[mid] > val):
retVal = search( arr , start , mid - 1 , val)
else:
retVal = search( arr , mid + 1 , end , val)
return retVal