Binary Search in a Sorted Array

How to find an element in a sorted array using Binary Search?
Please check out the video below for detailed explanation of the algorithm with animations.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

Binary search algorithm is used for solving many programming interview problems.
This algorithm is based on divide and conquer strategy to find a number in a sorted integer array.
Binary Search:
1. Take start = 0, end = length of array - 1.
2. Repeat following steps till start <= end:  
   a). Set mid = (start + end)/2.
   b). Check if array[mid] == num, then return mid.
   c). If num < array[mid], set end = mid - 1
   d). Else set start = mid+1
3. Return -1.


Algorithm Visualization




Code Snippet

			
package com.ideserve.saurabh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Binary Search</b><br>
 * Given a sorted integer array and an integer, find the index of the integer in the array. If not found, return -1.
 * 
 * Example: <br>
 * array = { 21, 32, 43, 74, 75, 86, 97, 108, 149 }
 * <br>
 * integer = 43
 * <br>
 * Output: 2
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=PWFCbWt7VwY">Binary Search Youtube Link</a> 
 *
 * @author Saurabh
 */
public class BinarySearch {
	
	public static int findElementBinarySearch(int[] array, int num) {

		if (array == null || array.length == 0) {
			return -1;
		}

		int start = 0;
		int end = array.length - 1;

		while (start <= end) {
			int mid = (start + end) / 2;
			if (array[mid] == num) {
				return mid;
			} else if (num < array[mid]) {
				end = mid - 1;
			} else {
				start = mid + 1;
			}
		}

		return -1;
	}
	
	public static void main(String[] args) {

		int array[] = { 21, 32, 43, 74, 75, 86, 97, 108, 149 };
		int num = 43;
		binarySearchTest(array,num);
	}
	
	public static void binarySearchTest(int array[], int num) {
		int index = findElementBinarySearch(array, num);
		System.out.println("Element " + num + (index >= 0 ? (" found at index " + index) : " not found!"));
	}
}
		

Order of the Algorithm

Time Complexity is O(log n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.


    Saurabh Kumar