Identify

we are asked to find a certain element from a sorted array, linked list, or matrix

Motive

whenever we are asked to find a certain element, the best algorithm you can use is the Binary Search

Steps

for an ascending-order set:
1. first, find the middle of start and end, an easy way to find the middle would be:
  
  middle = (start + end) / 2.
  
  but this has a good chance of producing an integer overflow so it’s recommended that you represent the middle as:
  
  middle = start + (end — start) / 2
2. if the key is equal to the number at index middle then return middle
3. if ‘key’ isn’t equal to the index middle:
4. check if key < arr[middle] - if it is reduce your search to end = middle — 1
5. check if key > arr[middle] - if it is reduce your search to end = middle + 1

Complexity

Time `O(log(n))`

Space `O(1)`

Common Problems