Binary Search in Java — Implementing Recursive Binary Search Algorithm
Searching and Sorting algorithms are popular algorithms in any programming language. They are the basis to understand the fundamentals of programming. One such popular searching algorithm is Binary Search in Java. In this article, I will tell you all about its implementation.
Below topics are covered in this article:
- What is Binary Search?
- Implementing Binary Search Algorithm
- Recursive Binary Search
Let’s get started!
What is Binary Search?
Binary Search in Java is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. It works only on a sorted set of elements. To use binary search on a collection, the collection must first be sorted.
When the binary search is used to perform operations on a sorted set, the number of iterations can always be reduced on the basis of the value that is being searched. You can see in the above snapshot of finding the mid element. The analogy of binary search is to use the information that the array is sorted and reduce the time complexity to O(log n).
Implementing Binary Search Algorithm
Let’s take a look at the below pseudo code to understand it in a better way.
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searchedSet low = 1
Set high = nwhile x not found
if high < low
EXIT: x does not exist.set mid = low + ( high - low ) / 2if A[mid] < x set low = mid + 1 if A[mid]> x
set high = mid - 1if A[mid] = x
EXIT: x found at location mid
end whileend procedure
Explanation:
Step 1: First, compare x with the middle element.
Step 2: If x matches with the middle element, then you have to return the mid index.
Step 3: Else, If x is greater than the mid element, then x can only lie in the right side half array after the mid element. Hence you recur the right half.
Step 4: Else, if (x is smaller) then recur for the left half.
That’s how you need to search for the element in the given array.
Let’s now see how to implement a binary search algorithm recursively. The program demonstrates the same.
Recursive Binary Search
public class BinarySearch {
// Java implementation of recursive Binary Search
// Returns index of x if it is present in arr[l..h], else return -1
int binarySearch(int a[], int l, int h, int x)
{
if (h >= l) {
int mid = l + (h - l) / 2;
// If the element is present at the middle itself
if (a[mid] == x)
return mid;
// If element is smaller than mid, then it can only be present in left subarray
if (a[mid] >x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present in right subarray
return binarySearch(arr, mid + 1, h, x);
}
// We reach here when element is not present in array
return -1;
}
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int a[] = { 20, 30, 40, 10, 50 };
int n = a.length;
int x = 40;
int res = ob.binarySearch(a, 0, n - 1, x);
if (res == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + res);
}
}On executing the above program, it will locate the element present at the particular index
Element found at index 2So this brings us to the end of the Binary Search in Java article. I hope you found it informative and helped you in understanding Java Fundamentals.
This brings us to the end of our blog on Advanced Java Tutorial. I hope you found this blog informative and added value to your knowledge.
If you wish to check out more articles on the market’s most trending technologies like Artificial Intelligence, DevOps, Ethical Hacking, then you can refer to Edureka’s official site.
Do look out for other articles in this series which will explain the various other aspects of Java.
1. Object Oriented Programming
5. Java String
6. Java Array
8. Java Threads
9. Introduction to Java Servlets
11. Exception Handling in Java
12. Java Tutorial
14. Java Programs
15. Kotlin vs Java
16. Dependency Injection Using Spring Boot
22. Socket Programming In Java
25. Library Management System Project in Java
26. Trees in Java
28. Top Data Structures & Algorithms in Java
30. Top 55 Servlet Interview Questions
34. Java Collections Interview Questions and Answers
35. How to Handle Deadlock in Java?
36. Top 50 Java Collections Interview Questions You Need to Know
37. What is the concept of String Pool in Java?
38. What is the difference between C, C++, and Java?
39. Palindrome in Java- How to check a number or string?
40. Top MVC Interview Questions and Answers You Need to Know
41. Top 10 Applications of Java Programming Language
42. Deadlock in Java
43. Square and Square Root in Java
Originally published at https://www.edureka.co on August 14, 2019.
