Amazon Prime

  • Algorithm
  • Searching

    Searching Algorithms


    Searching is the process of finding a desired element from a collection of available elements. For example, searching for a particular contact number in a phone directory. Desired phone number is called target and the phone directory is called search space. Search algorithms designed to find whether the target exists in the search space or anything. The search space can be an array or a list or it can be a database.

    Searching algorithms are mainly classified into two types :

    Linear Search

    In Linear Search, we sequentially traverse the array to check whether the element is matching with the given target element or not.

    Binary Search

    Binary Search algorithm works only if the elements of the array has some inherit ordering like elements of the array in ascending order by their values. In Binary Search we compare the middle element of the array with the target element and at each iteration we should be able to reduce the search space into half by using the sorting feature of the array.



    Video Explanation

    Linear Search Vs Binary Search

    Linear Search Binary Search
    Linear Search works even if elements are in random orderBinary Search works only if the elements are in sorted array
    In Linear Search, elements in the array will be checked one by one until we find the desired elementIn Binary Search random element will be checked and based on the values of random element further search process gets executed
    As elements checked sequentially, it is known as sequential searchevery iteration the array size gets reduced to half of its size, so it is known as interval search or logarithmic search
    Worst case time complexity is O(n)Worst case time complexity is O(log n)
    Linear search is efficient if array is smaller in sizeBinary search works efficient irrespective of the size of the array

  • Algorithm
  • Searching