Write a program to search an element from an array using Binary Search?
Additional Info
Please try to do it iteratively and recursively.
Please try to include the algorithm you used as well.
Hint: For doing binary search, the array should be already sorted.
package com.javajee.myBinarySearch;
public class BinarySearch {
int [] Numbers= {1,2,3,4,5,6,7};
int element=7;
String result=null;
public static void main(String[] args) {
String rIndex;
String iIndex;
BinarySearch bl= new BinarySearch();
int minIndex=0;
int maxIndex=(bl.Numbers.length)-1;
//calling recursive search algorithm
rIndex=bl.elemSearchRecurse(bl.Numbers,minIndex, maxIndex);
//Calling iterative algorithm
iIndex=bl.elemSearchIter(bl.Numbers, minIndex, maxIndex);
System.out.println(rIndex);
System.out.println(iIndex);
}
//Using Recursive algorithm
public String elemSearchRecurse(int[] Array,int min, int max){
if (max<min){
result="value not found";
}
else{
int midIndex=midValueCalc(min, max);
if(Array[midIndex]>element){
elemSearchRecurse(Numbers, min, midIndex-1);
}
else if(Array[midIndex]<element){
elemSearchRecurse(Numbers, midIndex+1, max);
}
else{
result="index of element in recursive algorithm is"+midIndex;
}
}
return result;
}
//Using Iterative algorithm
public String elemSearchIter(int[] Array,int min, int max){
String value=null;
while(max>=min){
int midIndex=midValueCalc(min, max);
if (Array[midIndex]>element){
max=midIndex-1;
}
else if(Array[midIndex]<element){
min=midIndex+1;
}
else{
value="Index of element found through iterative is"+midIndex;
return value;
}
}
return "ELEMENT NOT FOUND";
}
//mid index calculator
public int midValueCalc(int min, int max){
return (min+((max-min)/2));
}
}
NOTE:
Binary search returns the index of searched element as result.
Element to be searched is compared with value of the middle element (mid) of the array.
if element=middle element, then index of middle element is returned as result.
if element < middle element, process continues with elements on the left side of the array. (sub array to the left)
if element > middle element, process continues with elements on the left side of the array. (sub array to the right)
This process continues until all elements are compared or when a match is found.
It can be done both recursively and iteratively.