Write an algorithm to find an element in an sorted array

Topic: Binary Search

Difficulty: Easy.

Companies who previously asked this: Amazon.

Objective: Write an algorithm to find an element in a sorted array.

Input: A sorted array, and a primary key. (We will assume the sorted array is given and the key element is made known to us as well.)

Expected Output: Return true if element is found, else return false.

Our Approach: We will first identify an element to be found as a key (called the key element). We will compare the middle element of the array with the key element, if the key element equals the middle element, you've found your element, the program ends, return true. If key is greater than the middle element, remove the first half of the array because you won't find your key in the first half and do the recursive search on the right half of the array and vice versa.

Time Complexity: O(logN) (Because we are eliminating half of the array with every comparison.)

Graphical Illustration

Pseudocode

If(mid_element equals primary_key)
  return true;
else if (mid > key)
  do recursive search on the right half of the array.
else
  do recursive search on the left half of the array.

Full program

public class BinarySearch {
	private int [] numbersList;
	private int number;

	public BinarySearch(int [] numbersList){
		this.numbersList = numbersList;
	}
	public Boolean Search(int low, int high, int number){
		if(low > high){
			return false;
		}
		int mid = low + ((high - low) / 2);
		if(numbersList[mid] == number) return true;
		else if (numbersList[mid] > number) return Search(low, mid - 1, number);
		else return Search(mid + 1, high, number);
	}

	public static void main(String args[]){
		int [] numbers = {23,25,38,40,44,54,57,68,79};
		int number = 79;
		BinarySearch s = new BinarySearch(numbers);
		System.out.println("Is the number " + number + " present in the list of numbers?: " + s.Search(0, numbers.length-1, number));
		number = 56;
		System.out.println("Is the number " + number + " present in the list of numbers?: " + s.Search(0, numbers.length-1, number));
	}
}

Output: