Topic: Binary Search
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.)
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.
Is the number 99 present in the list of numbers?: true
Is the number 56 present in the list of numbers?: false