There are two types of searching are possible. First is linear search and second is binary search. In this article we explain about the binary search program, if you want to learn about what is linear search and how it works? see this article Linear Search.

The linear search and binary search are used to find the key element in a given multiple elements and displays the position or index of the key element in the array. In the binary search we need to find mid element because we perform this searching operation on each half of array.

Following is the pseudo code of binary search program:

binary_search(Arr, target):
low = 1, high = size(Arr)
while low <= high:
mid = low + (high-low)/2
if Arr[mid] == target:
return mid
else if Arr[mid] < target:
low = mid+1
else:
high = mid-1
// target was not found

Program:

java implementation of recursive Binary Search

In the implementation of recursive binary search program we will use the recursively method for finding the index of element. Here we use binarySearch() is the method For search the key element recursively. If the key element is present then it return position and if key element not present then return -1.

class BinarySearch
{
// Returns index of x if it is present in arr[l..r], else
// return -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2; // If the element is present at the middle itself
if (arr[mid] == x)
return mid; // If element is smaller than mid, then it can only
// be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid- 1, x);
// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present in array
return -1;
}
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = {2,3,4,10,40};
int n = arr.length;
int x = 10;
int result =
ob.binarySearch(arr,0,n-1,x);
if (result == -1)
   System.out.println("Element not present");
else
   System.out.println("Element found at index "+result);
}
}

Output:
Element is present at index 3

java implementation of recursive Binary Search

Program:

Iterative implementation of Binary Search

In the implementation of the iterative binary search algorithm we use the iterative approach instead recursive approach. The following programs works iterative manner.

class BinarySearch
{
// Returns index of x if it is present in arr[], else
// return -1
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int m = l + (r-l)/2; // Check if x is present at mid
if (arr[m] == x)
return m; // If x greater, ignore left half
if (arr[m] < x)
l = m + 1; // If x is smaller, ignore right half
else
r = m - 1;
} // if we reach here, then element was not present
return -1;
}
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = {2, 3, 4, 10, 40};
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, x);
if (result == -1)
   System.out.println("Element not present");
else
   System.out.println("Element found at index "+result);
}
}

Output:
Element is present at index 3

Iterative implementation of Binary Search

Output of the both programs are same but the used methods or approach are different. In this article you learn about binary search. Algorithm of binary search and the working of binary search.

If you are new in java and don’t know the what is binary search. You are confuse about binary search or you can’t understand the working of binary search. Don’t worry about that see Binary Search article so you can understand it easily.

I hope you would like this article. If you have any query then comment me below. Please comment me you like this article or not.

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top