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

Lets say we have an sorted array.

**Algorithm:**

- Initialize
`first=0`

and`last=sortedArray.length-1`

- compute mid and compare
`sortedArray[mid]`

with element to be searched - If element to be searched is less than
`sortedArray[mid]`

then element lies in left part of the mid, so`last=mid-1`

- if element to be searched is greater than
`sortedArray[mid]`

then element lies in right part of the mid, so`first=mid+1`

. - if element to be searched is equal to
`sortedArray[mid]`

, then return index - Repeat above process until first is less than last.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
public static int binarySearch(int[] sortedArray, int elementToBeSearched) { int first = 0; int last = sortedArray.length - 1; while (first <= last) { int mid = (first + last) / 2; // Compute mid point. if (elementToBeSearched < sortedArray[mid]) { last = mid-1; // repeat search in first half. } else if (elementToBeSearched > sortedArray[mid]) { first = mid + 1; // Repeat sortedArray in last half. } else { return mid; // Found it. return position } } return -1; // Failed to find element } |

**Example:**

Now lets assume our sorted array is:

1 2 3 |
int[] sortedArray={12,56,74,96,112,114,123,567}; |

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]`

.

0th iteration : n

1th iteration: n/2

2nd iteration n/4

3rd iteration n/8.

Generalizing above equation:

For ith iteration : n/2^{i}

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

^{i};

2

^{i}=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:**

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 |
package org.arpit.java2blog; public class BinarySerarchMain { public static int binarySearch(int[] sortedArray, int elementToBeSearched) { int first = 0; int last = sortedArray.length - 1; while (first <= last) { int mid = (first + last) / 2; // Compute mid point. if (elementToBeSearched < sortedArray[mid]) { last = mid-1; // repeat search in first half. } else if (elementToBeSearched > sortedArray[mid]) { first = mid + 1; // Repeat sortedArray in last half. } else { return mid; // Found it. return position } } return -1; // Failed to find element } public static void main(String[] args) { int[] sortedArray={12,56,74,96,112,114,123,567}; int indexOfElementToBeSearched=binarySearch(sortedArray,74); System.out.println("Index of 74 in array is: " +indexOfElementToBeSearched); int indexOfElementToBeSearchedNotFound=binarySearch(sortedArray,7); System.out.println("Index of 7 in array is: " +indexOfElementToBeSearchedNotFound); } } |

Index of 7 in array is: -1

## Further reading:

That’s all about binary search in java

Thanks for the post!, greate job.