Binary Search

Searching technique is the process to find an element within the lists of elements.

There are two kinds of searching algorithm available to us.

• Linear Search
• Binary Search

Linear Search :-  is simplest approach to find elements one by one in the list of elements. The time complexity of Linear Search algorithm is O(n).

Binary Search: It is faster than Linear Search and having time complexity O(Log n). It works on sorted list of elements by repeatedly dividing the search interval in half. It starts with an interval 0 to max length of list. Here we are calculating middle element in the list as below for the first time.

int beg= 0;

end= a.length-1;//initially high is set to the last element

mid = (beg+end)/2;

Then we have to compare the middle element from the search item as per below scenarios.

• If a[mid] > search_item, recalculate mid element and reset beg and end. Initialize end= mid-1,beg=0
• if a[mid]<search_item, then beg = mid+1 and end = length of the list
• if a[mid]==search_item then we found the element at index mid.

From this we are diving the list into halves until we found the search item.

Java Binary Search Example using recursion

public class BinarySearchEx {
public static void main(String[] args) {
int a[]={1,2,3,4,18};
binarySearch(a,4,0,a.length-1);
}
public static void binarySearch(int a[],int element,int low,int high)
{
if(element>=a[low] && element<=a[high]) {
int mid = (low+high)/2;
if (a[mid] == element) {
System.out.println("Element found at index "+mid);
} else if (element > a[mid]) {
binarySearch(a, element, mid + 1, high);
} else if (element < a[mid]) {
binarySearch(a, element, 0, mid - 1);
}
}
}
}

Java Binary Search Example using Loop

public class BinarySearchEx {
public static void main(String[] args) {
int a[]={1,2,3,4,18};
binarySearchWithLoop(a,18);
}
public static void binarySearchWithLoop(int a[],int element){
int beg = 0;
int end = a.length-1;
int mid = 0;
while(beg<=end){
mid = (beg+end)/2;
if(a[mid]==element){
System.out.println("Element found at index "+mid);
break;
}else if (element > a[mid]){
beg = mid+1;
}else {
end = mid-1;
}
}
}
}