Write an algorithm to find an element in an sorted array
Updated: Feb. 25, 2021 — Training Time: 2 minutes
Overseen by: Archangel Macsika
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:
Is the number 99 present in the list of numbers?: true
Is the number 56 present in the list of numbers?: false