Binary Search In Java And It's Complexity

Have you ever used a word dictionary of any language?? You must be thinking that what word dictionary has to do with binary search, right? Well, it has. Binary search is exactly similar to the searching for a word in a dictionary!!

By the way, binary search has one precondition- data structure needs to be present in sorted order. Like a dictionary has words arranged in sorted order. We can sort data structure using various sorting algorithms.

Steps to search for a word in a dictionary?

1. Go to the middle of the dictionary.
2. If you find the word then stop here else go to step 3.
3. See if the word shall come after middle of the dictionary or before.
4. If it comes after the middle of the dictionary then take middle till end of the dictionary as a new dictionary & repeat steps 1-4.
5. If it comes before the middle of the dictionary then take middle till start of the dictionary as a new dictionary & repeat steps 1-4.
6. If you are at the extreme end or extreme start of the dictionary then it means the word you are looking for is not in the dictionary.

Ok, it's time to code above logic in Java.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

/** * BINARY SEARCH JAVA PROGRAM */ package javagreedy.blogspot.com; import java.util.Arrays; /** * @author javagreedy.blogspot.com * */ public class BinarySearchApp { public static void main(String[] args) { String[] dictionary = new String[]{"Dog", "Apple", "Ant", "Ball", "Elephant", "Cat", "Frog", "Fish"}; // unsorted array of words Arrays.sort(dictionary);// we have sorted it using existing sort api // provided by Java System.out.print("Dictionary contains: "); for (String word : dictionary) { System.out.print(word + " "); // display the sorted dictionary } System.out.println();// line break binarySearch(dictionary, "Ant"); // binary search for Ant in dictionary binarySearch(dictionary, "Tiger"); // binary search for Tiger in // dictionary } private static void binarySearch(String[] dictionary, String wordToFind) { int start = 0; // dictionary start int end = dictionary.length - 1;// dictionary end int middle = (start + end) / 2;// middle of the dictionary // base condition while (start <= end) { // check if the word is at middle if (dictionary[middle].equals(wordToFind)) { System.out.println(wordToFind + " is found at location " + middle); break;// exit } else if (dictionary[middle].compareTo(wordToFind) < 0) {// check // if // wordTofind // is // after // middle start = middle + 1;// reset start } else { end = middle - 1;// if wordTofind is before middle then reset // end } middle = (start + end) / 2;// find middle of new dictionary } if (start > end) // unexpected condition System.out .println(wordToFind + " is not present in the dictionary"); } }

Output:

1 2 3

Dictionary contains: Ant Apple Ball Cat Dog Elephant Fish Frog Ant is found at location 0 Tiger is not present in the dictionary

Well, Java already provides a method for binarySearch in class java.util.Arrays. You can use it as below-

int index = Arrays.binarySearch(dictionary,"Ant");

What is the time complexity of binary search?

Worst  Case:  Worst case will be when the element we are searching for is not present in the data structure. In the second execution of above program where we searched for "Tiger". Each time we divided dictionary into half. We went on doing this until there were no further division possible. If you see this looks similar to the logarithmic time complexity. Suppose we have 8 words then we will divide dictionary in the following ways- 

1. middle = 8/2 = 4

2. middle = 4/2 = 2

3. middle = 2/2 = 1 No further division is possible.

Here, we divided dictionary 3 times. Mathematically: log(8) = 3 where log base is 2 as we are dividing dictionary each time by 2. So, if we have n elements in data structure then worst case complexity for binary search would be log(n).

Best Case: At the very first execution, we directly searched for the word in middle of the dictionary. And if that is the word we are looking for then this is the best case. Irrespective of the number of words in a dictionary we will always have to check to divide the dictionary only once if it's the best case. So, best case complexity becomes O(1).