Performing Binary Search on a Sorted Array

This post is to make you understand:

1) How to perform a Binary search on a sorted Array of numbers.
2) How to compute the complexity of Binary Search.

Binary Search algorithm works based on divide and conquer method. we have to split the given array into two parts and then perform the search. This process will be repeated in a loop until the firstIndex of the array is less than the lastIndex.

Let us assume that the given sorted Array is 'sortedArr' and the element to be searched as 'elementToBeSearched'.
Initialize the 'firstIndex' as 0 and the 'lastIndex' as last=sortedArr.length-1.

1) Algorithm Steps:

1) Compute the midIndex by (firstIndex + lastIndex) / 2;
2.1) If the element to be searched is lesser than sortedArr[midIndex], then we can decide that the element lies in left part of the sortedArr from midIndex. So assign lastIndex = midIndex.
2.2) If the element to be searched is greater than sortedArr[midIndex], then we can decide that the element lies in right part of the sortedArr from midIndex. So assign firstIndex = midIndex + 1.
2.3) If the element to be searched is equal to sortedArr[midIndex], then return the index and print the result.
3.1) If the element to be searched  is equal to sortedArr[lastIndex], then return lastIndex and print the result.
3.2)  If the element to be searched  is equal to sortedArr[firstIndex], then return firstIndex and print the result.
4) Repeat the above steps until the firstIndex is less than the lastIndex.
5) If the element is not found from steps 2 to 4, then return -1.

Lets see the complete program in Java now:

public class BinarySearch {

public static int binarySearch(int[] sortedArr, int elementToBeSearched) {
int firstIndex = 0;
int lastIndex = sortedArr.length - 1;

while (firstIndex < lastIndex) {
int midIndex = (firstIndex + lastIndex) / 2;

if (elementToBeSearched < sortedArr[midIndex]) {
lastIndex = midIndex;
} else if (elementToBeSearched > sortedArr[midIndex]) {
firstIndex = midIndex + 1;
} else {
return midIndex;
}

if (elementToBeSearched == sortedArr[lastIndex]) {
return lastIndex;
} else if (elementToBeSearched == sortedArr[firstIndex]) {
return firstIndex;
}
}

return -1;
}

public static void main(String[] args) {

int[] sortedArr = { 12, 56, 74, 96, 112, 114, 123, 567 };
int indexOfElementToBeSearched = binarySearch(sortedArr, 12);
System.out.println("Index Found at Index: "
+ indexOfElementToBeSearched);

}

}

2) Computing Complexity:

Given the sortedArr is {12,56,74,96,112,114,123,567}. For searching the element 74, the following will be the complexity of the Algorithm.

In each of the iteration, the number of elements involved in the search is getting reduced by half.

So complexity for each iteration will be as follows:

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

For ith iteration : n/2 power i

So iteration will end , when we have 1 element left i.e. for any i, which will be our last iteration:
1=n/2  power i;
2  power i=n;
after taking log on both sides, it becomes
i= log(n);
so it concludes that number of iteration requires to do binary search is log(n).

and hence the complexity of binary search algorithm is log(n).

In the above example, n = 8. log(8) = 3 proves that we needed only 3 iterations to find the element.

Happy learning!!!