binary search algorithm

Binary search algorithm is one of the fastest way to identify the element from an sorted array. It is also the commonly asked data structure interview questions.

It works based on divide and conquer mechanism. It will divide the given array into 2 parts and discard the one part. So it will works faster for a big array compared to linear search.

Time complexity of Binary Search is O(logn)

Below is the give array structure

With the above given array we have to find the position of 9, Using linear search we can find easily, But the time complexity will be O(N)

Below is java code snippet to find the position using Binary Search

public class BinarySearchExample {

	private int binarySearch(int[] array, int target) {
		int leftIndex = 0;
		int rightIndex = array.length - 1;
		while (leftIndex <= rightIndex) {
			// find the middle Index
			int middleIndex = (leftIndex + rightIndex) / 2;
			if (array[middleIndex] == target) {
				return middleIndex;
			}
			if (target > array[middleIndex]) {
				// ignoring the left side of array
				leftIndex = middleIndex + 1;
			} else {
				// ignoring the right side of array
				rightIndex = middleIndex - 1;
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] i = { 2, 3, 5, 6, 7, 9,10 };
		int targetNumber = 9;
		BinarySearchExample object = new BinarySearchExample();
		int output = object.binarySearch(i, targetNumber);
		System.out.println(output);
	}

}

Output

5