Binary Search in a Sorted Array

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.

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)