Linear and Binary Search Algorithms in JavaScript and Ruby

Search Algorithms allow us to solve a specific search problem, and retrieve information from the database.
There are many ways to do so, some are faster than others, some are better in some situations but not in others, so which search algorithm should we use?
It depends on two values that describe the performance of the algorithms in terms of run time:

Big O notation (O): how much time does it take to the program to run at max (in the worst possible scenario)

Big Omega notation (Ω): in the best scenario, how many steps does it take to the program to find the searched item?

LINEAR SEARCH:

Searching from left to right in the memory grid, sequentially until a match is found or until all the elements have been asked without success, we are essentially following a line.

Example: We have a set of 8 lockers in front of us, inside each one there is a card with a number written on it. All lockers are closed.
How do we find the locker with the card that has 2 written on?
With Linear Search, we open each locker (one locker at a time) until we find the card with the number 2.

JavaScript:

function linearSearch(arr, searchedValue){
  for (let i = 0; i < arr.length; i++){
      if (arr[i] === searchedVal){
         return i
      }
   }
  return -1    //if not found
}

Ruby:

array = [4,1,6,2,5,7,9,8]
searchItem = 2
def linear_search(array, searchItem)
  index = 0
  while index < array.length
      if array[index] == searchItem
        return index
      end
      index += 1
  end
  "Not found"
end
puts linear_search(array, searchItem)
#=> 3 (index where to find the element that we are searching for)

How much time does Linear Search take in the worst possible case? For example if the card with number 2 doesn’t exist in any lockers, or if it’s located in the last locker.
O(n): Linear Search can take up to the full length of the array (‘O on the order of n’), it can take up to n steps.

But how much time and/or how many steps would it take to find the searched item in the best possible scenario? For example, if the card with the number 2 is located in the first element of the array, at index 0.
Ω(1): with Linear Search in the best possible scenario, it would only take 1 step to find the searched item, in our example: open the first locker and voilà, there it is.

BINARY SEARCH:

If we know that the numbers inside our lockers are sorted, we can proceed by opening the mid locker, if the number on the card of the middle locker is higher than 2, we know to look to the left, but if it’s lower we can go ahead an look to the lockers to the right. And so on until we find it.

JavaScript:

function binarySearch(arr, searchedVal){
  let min = 0
  let max = arr.length - 1
  while (min <= max){
    let middle = Math.floor((min + max) / 2)
    let currentElement = arr[middle]
    if (currentElement < searchedVal){
        min = middle + 1
    }else if (currentElement > searchedVal){
        max = middle - 1
    }else {
        return middle
    }
  }
return -1
}

Ruby:

array = [0,1,3,2,5,7,9,8]
searchItem = 2
def binary_search(array, searchItem)
  first = 0
  last = array.length - 1
 while first <= last
  i = (first + last) / 2
    if array[i] == searchItem
        return "#{searchItem} found at position #{i}"
    elsif array[i] > searchItem
        last = i - 1
    elsif array[i] < searchItem
        first = i + 1
    else
        return "#{searchItem} not found in this array"
    end
 end
end
puts binary_search(array, searchItem)
#=> 2 found at position 3

We use array.length — 1 because arrays are 0 indexed, so the last element is found at index:length — 1.

Run time in the worst possible scenario: O(log n). The time/steps needed to solve the problem will grow at the increase of the size of the array, but not proportionally, because we are dividing the array in two, so it will increase on the order of log n.

Run time in the best possible scenario: Ω(1). Like Linear Search, the best possible scenario in the case of a Binary Search is that the searched item is found right away, in the element of the array in the middle.