Binary Search Java: A Guide

How to Write a Binary Search Algorithm in Java

Computers do not search through items like humans do. Whereas humans can change their approach to finding something, computers need to be given specific instructions on how to locate a particular item. That’s where standard algorithms are useful.

Binary searches are an example of a standard algorithm. They are used to find an element in a sorted array of items. In this guide, we’re going to talk about what binary searches are, how they work, and how you can implement them in Java. We’ll walk through two examples of a binary search: one using the recursive approach, and the other using the iterative approach.

Let’s get started!

What is a Binary Search?

A binary search is a search algorithm that locates the position of an element in a sorted array.

Binary searches start by dividing a list in half. The search will then compare the middle number to the number for which the algorithm is searching.

If the number is smaller than the middle number, this process is repeated for the lower half of the list; otherwise, this process is repeated for the upper half of the list.

Binary searches are more efficient than linear searches, another common type of search. This is because each time the algorithm looks for an item, it reduces the number of items to search through by a factor of two.

Binary searches can only be executed on a sorted list of items. This means that if you don’t already have a sorted list, you will need to sort it using a sorting algorithm before running a binary search.

How do Binary Searches Work?

Binary searches can be implemented in two ways: iteratively or recursively.

An iterative binary search is one where loops are used to search for an item in a list. A recursive binary search uses a function that calls itself again and again to find an item in a list. Recursive binary searches use the divide and conquer approach to find an item.

You can learn more about recursion in our guide to Java recursion.

The general algorithm for implementing a binary search is the same no matter which approach you decide to use.

Consider the following list:

We’re going to search for the number 7 in our list. To start, we are going to set two pointers which represent the lowest and highest positions in our list:

Next, we have to find the middle element in our array. We can do this by using the formula: (low + high) / 2. In this case, the middle element is 8.

Our algorithm will compare whether the middle element is equal to the one for which we are searching. If the numbers are equal, our search can stop. We’re looking for the number 7, which is not equal to 8, so our search continues.

Our algorithm compares whether the number for which we are searching is greater than the middle number. If it is greater, our search will begin all over again on the top half of our list. This is performed by setting low to be equal to low = middle_number + 1. Otherwise, the search will start again on the bottom half of our list.

7 (the number we’re searching for) is not greater than 8 (the middle number). This means that our algorithm is going to search through the bottom half of our list. We do this by setting our “high” value to high = middle_number – 1.

Now, our algorithm is going to repeat our search. We’ll compare the middle number, 7, with the one for which we are searching. We are looking for the number 7, so our search algorithm stops. We’ve found the position of 7 in our list!

How to Implement a Java Binary Search

We’re done with the theory so now all that is left to do is implement our search. It’s one thing going through and searching a list by ourselves; it’s another thing entirely to code an algorithm that does the search for us.

We’ll start by writing a program that implements a Java binary search using the iterative method.

Iterative Method

Let’s define a function called searchItems, which searches through our list of items:

class BinarySearch {
	int searchItems(int array[], int searchingFor, int low, int high) {
		while (low <= high) {
			int middle = low + (high - low) / 2;
			if (array[middle] == searchingFor) {
				return middle;
			} else if (array[middle] < searchingFor) {
				low = middle + 1;
			} else {
				high = middle - 1;
			}
		}
		return -1;
	}
}

This function searches through our list of items using the binary search.

Our function accepts four parameters: the list through which we want to search (array), the item for which we are searching (searchingFor), the low number (low), and the high number (high).

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

Inside our function we have declared a while loop. While the value of “low” is less than or equal to “high”, the loop will execute.

Our while loop begins by calculating the middle number. It then checks to see whether the value at that position is equal to the one for which we are searching.

If those numbers are equal, that value is returned to our main program. If not, our program checks if the value at the middle position is less than the one for which we are searching. If it is, a new low value is set.

Otherwise, a new high value is set so our list can search again in the upper half of the list.

If our item cannot be found, -1 is returned. We’ll use this to tell our main program that the list item cannot be found in a minute.

Our code doesn’t do anything yet because we haven’t written our main program. Add the following code below the searchItems() function in your BinarySearch class:

public static void main(String args[]) {
		BinarySearch newSearch = new BinarySearch();
		int listToSearch[] = { 6, 7, 8, 9, 10 };
		int listLength = listToSearch.length;
		int numberToFind = 7;
		int findNumber = newSearch.searchItems(listToSearch, numberToFind, 0, listLength - 1);
		if (findNumber != -1) {
			System.out.println(numberToFind + " was found at index position " + findNumber + ".");
		} else {
			System.out.println(numberToFind + " was not found in the list.");
		}
	}

Let’s run our code and see what happens:

7 was found at index position 1.
We've found the position of our number!

Our main program starts by initializing an instance of the BinarySearch class. We use this to start our search latre in the program. We then define three variables:

• listToSearch: The list through which we want to search.
• listLength: The length of the list.
• numberToFind: The number that we’re looking for in the list.

Once we have defined these variables, we use the searchItems() function we declared earlier to find a number in our list. We assign the value this function returns to the variable “findNumber”.

If findNumber is not equal to -1 – which means our number has been found – then the index position of the item that we’re searching for is printed to the console. Otherwise, a message is printed to the console telling us the number could not be found.

Recursive Method

A recursive approach can be taken to implement a binary search. This is where you write a function that calls itself until a specified item is found.

Let’s start by defining a function that performs our binary search recursively:

class BinarySearch {
	int searchItems(int array[], int searchingFor, int low, int high) {
		if (high >= low) {
			int middle = low + (high - low) / 2;
	
if (array[middle] == searchingFor) {
				return middle;
			} else if (array[middle] < searchingFor) {
				searchItems(array, searchingFor, middle + 1, high);
			} else {
				searchItems(array, searchingFor, low, middle - 1);
			}
		}
		return -1;
	}
}

This function implements our binary search in a different way. Instead of using a while loop, we use an if statement to check if the high number is equal to or less than the low number.

If this statement evaluates to true, our search begins. Otherwise, -1 is returned, which tells our program that a specified item could not be found in the list.

Inside our if statement, we check if the value of the middle number is equal to the one for which we are searching. If it is, we return that number to our main program.

If this statement doesn’t evaluate to true, our program checks to see if the number in the middle position is less than the one for which we are searching. If it is, the searchItems() method will be run again, but this time our low number will be equal to one greater than our middle number. This divides the number of items our list needs to search through by two.

Otherwise, searchItems() is run again and the value of the highest number is made equal to the middle number minus one. This means that we can refine our search only to the left half of our list.

We can use the same main function that we wrote earlier to test out our code. Let’s see what happens when we run our code:

7 was found at index position 1.

Our item was found again! This time, we used a recursive approach to finding our number instead of an iterative one.

Complexity Analysis

The binary search algorithm has a best case complexity of O(1). This happens when the first item that is compared by the algorithm is the one that is being searched for.

A binary search algorithm has an average and worst case complexity of O(log n). This means that, in most cases and in the worst case, the speed of the algorithm slows logarithmically depending on how many items the list has to search through.

Conclusion

Binary searches are used to find the position of an element in a sorted list. Binary searches compare the item in the middle of a portion of an array to the number for which the algorithm is searching.

Binary searches are more efficient than linear searches. This is because every time a search is performed the number of values that need to be searched through is divided by two.

Now you’re ready to implement a binary search in Java like an expert programmer.