How to Implement Binary Search Algorithm in Swift and Java

Binary search algorithm is a searching algorithm which can search through sorted lists in O(log n) time.

It is an example of Divide and Conquer technique which divides the search problem in smaller half and keep searching the element. It’s an efficient search algorithm if you have a sorted list.

Below are the steps to explain the divide and conquer approach:

Binary Search Divide and Conquer Steps

Let’s assume we are searching for X

1. Divide – Compare the middle element with the X, if the element not found then divide the list in two parts.
2. Conquer – Recurse in one subarray where the X might be based on the comparison result in Divide step.
3. Combine – You don’t have to do anything.

Binary Search Algorithm

Here is a pseudo-code for the algorithm (Source Wikipedia):

1. Set L to 0 and R to n − 1.
2. If L > R, the search terminates as unsuccessful.
3. Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
4. If A_m < T, set L to m + 1 and go to step 2.
5. If A_m > T, set R to m – 1 and go to step 2.
6. Now A_m = T, the search is done; return m.

The intent for Binary search is very simple. It try to judge the position of the element by comparing the middle element to the search element.

If the middle element is smaller then the search element, it should reside in the upper half of the list. Otherwise the element should be in the lower half.

The algorithm will divide the list and will search the element in the respective half. It will keep using the divide method till it exhaust all the elements or find the correct element.

Swift Implementation

Here is the swift implementation:

https://gist.github.com/SanjeevMohindra/08f061a37f6843bafeedf628f5a24b49

We will set the right and left boundaries the list. We will initialise it with the actual length of the list at first and then will keep the pointers moving according to the comparison results.

Now we will compare the search element with the middle element in a while loop till our left boundary is not greater then right boundary. If that happens, it means that we have exhausted all out elements and have not found the correct element. We will return -1 in this case.

If middle element is smaller then search element, we will move the left boundary to middle element plus one. This will create a subarray of upper half of the elements.

If middle element is greater then search element, we will move the right boundary to middle element minus one. This will create a subarray of lower half of the elements.

This should provide an easy and fast way to scan through the sorted list and give back an location of the specified element.

Java Implementation

Here is an Java implementation

https://gist.github.com/SanjeevMohindra/9f8cdb16650d2f1895c0eeadf6bb796b

The implementation is similar to what we have done for Swift implementation. So you can check the explanation of Swift implementation for any clarifications.

Use comment section for any queries you have on Binary Search Algorithm.