Write an algorithm to find an element in an sorted array


Updated: Nov. 27, 2020 — Training Time: 2 minutes
Overseen by: Archangel Macsika
All Training Resources

Scroll for more menu list

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

Binary Search - Write an algorithm to find an element in a sorted array.

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

Output:

Is the number 99 present in the list of numbers?: true

Is the number 56 present in the list of numbers?: false

Was this training resource helpful?