Binary search in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

In this post, we will see how to perform binary search in java using divide and conquer method.When you want to find a value in sorted array, we use binary search and we will also see how to compute time complexity of binary search.
Lets say we have an sorted array.

Algorithm:

  1. Initialize first=0 and last=sortedArray.length-1
  2. compute mid and compare sortedArray[mid]  with element to be searched
  3. If element to be searched is less than sortedArray[mid] then element lies in left part of the mid, so last=mid-1
  4. if element to be searched is greater than sortedArray[mid] then element lies in right part of the mid, so first=mid+1.
  5. if element to be searched is equal to sortedArray[mid], then return index
  6. Repeat above process until first is less than last.
Example:
Now lets assume our sorted array is:
and we want to search for 74 in above array. Below diagram will explain how binary search will work here.

When you observe closely, in each of the iteration you are cutting scope of array to the half. In every iteration, we are overriding value of first or last depending on sortedArray[mid].

So for
0th iteration : n
1th iteration: n/2
2nd iteration n/4
3rd iteration n/8.

Generalizing above equation:
For ith iteration : n/2i

So iteration will end , when we have 1 element left i.e. for any i, which will be our last iteration:

1=n/2i;
2i=n;
after taking log
i= log(n);

so it concludes that number of iteration requires to do binary search is log(n) so complexity of binary search is log(n)
It makes sense as in our example, we have n as 8 . It took 3 iterations(8->4->2->1) and 3 is log(8).
Code:

when you run above program, you will get below output:

Index of 74 in array is: 2
Index of 7 in array is: -1

That’s all about binary search in java

Was this post helpful?

Comments

Leave a Reply

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