Searching: Binary Search

Binary Search

Okay, so how do you think we can search for a paticular element in an array?
One obvious way will be to loop through the array and return true at which the element is found and to return false if it doesn't exist in the array. But the problem with this algorithm known as linear search is that it can very quickly turn out to be very costly in terms of space and time as this algorithm takes O(n) or linear time. This turns out to be highly costly for a large number of elements in an array.

#Linear Search -->
def linear_search(array , n ):
  for i in array:
    if i == n :
      return True

So, the solution to this is to use an algorithm called binary search. Binary search is an algorithm that works on the divide and conquer technique and is also extremely efficient.It works on O(logn). But the only catch to this algorithm is that the array it is being applied on needs to be sorted.

#Binary Search --> 
def binary_search(array, n ):
  #Setting up search space variables and found flag
  high = len(a) - 1 
  low  = 0          
  found = False
  #search begins from while loop
  while( first <= last and not found ):
    #calculating midpoint
    mid = (low + high) // 2
    #check if element at midpoint is equal to the element being searched
    if array[mid] == n :
      return True
    else :
      if item < array[midpoint] :
      # if item is larger than the item at midpoint then the search space is cut into half
        high = midpoint - 1
      else :
        #if item is larger than the item at midpoint, low is set to be the index next to midpoint
        low = midpoint + 1
  return found

To use binary search is the obvious choice if the list is ordered but if it is not ordered, either to use linear search or binary search depends on the size of the list as for an unordered list it first needs to be sorted. Binary search along with python's sort method is a little more costlier than linear search in most cases.

Demo for binary search: