This implementation of Binary Search algorithm is aim to be one of the most simplest. The elements are in sorted array.
If the search element (item) value is bigger than the middle value - > take the right part and apply the algorithm on it.
If the search element is the middle element - the recursion stoops - > returns the element.
The recursion also stops if there is no such element in the array - the checks are done till start index is lest than the end index. Another interesting point is that the calculation of the middle index is done by accumulating the start index (in the beginning =0) : int index = start + (end-start)/2;
When we are somewhere in the array - the start will not be always equals to 0 as it is in the beining but will really depends on the search element and the elements in the array.
// Binary search in sorted array
public class BinarySearch
{
public static void main(String[] args)
{
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
22, 34, 56, 78, 90, 112, 113, 224};
int result = find(arr, Integer.parseInt(args[0]));
System.out.println(result);
}
public static int find(int[] arr, int item)
{
return find(arr, 0, arr.length, item);
}
public static int find(int[] arr, int start, int end, int item)
{
if(arr==null)
return -1;
if(arr.length==0)
return -1;
if(start
{
int index = start + (end-start)/2;
int middle = arr[index];
if(item < middle)
return find(arr, start, index, item);
else if(item>middle)
return find(arr, index+1, end, item);
else
return index;
}
return -1;
}
}
Posts
