Searching Algorithms, Part 2.

This post focuses on Week 8 content.

We can show using big-Oh that a linear search, given the worst case scenario;
when what we are searching for does not exist, is in $\mathcal{O}(n)$

I learn't that this was true using a combination of source material from my CSC108 class,
which is currently covering algorithm complexity, and the tutorial problems, which permit such a method of analyzing algorithms.

Let's us look at the code for a basic linear search:

1    def linear_search(L, value):
2        """ (list, object)-> int
3    
4        Return index for first occurrence of value in list L.
5        If value is not in L return -1.
6    
7        >>>linear_search(['a','b','c','d','c'],'c')
8        2
9        >>>linear_search([1,2,3,4,5],10)
10       -1
11       """
12   
13       for index in range(len(L)):
14           if L[index] == value:
15               return index
16       return -1

Here for an input of size $n$, the amount of steps taken will be proportional to $n$
as we can see from lines 13 of the code:

the number of loops is dependent on the length of list $L$ ( which is $n$). The complexity is independent of the code inside the loop in lines 14, 15.

So, what does it mean for Linear Search to be in $\mathcal{O}(n)$?

It just means it is really, really bad, and that we can do much better.

I personally think it was a pity that the course material did not introduce us to a substantially better
search algorithm. So hence I feel it is my responsibility to introduce to you....*drumroll*

Binary Search!

Here is the code for binary search that I wrote:

def binary_search(L, v):
    """(list, object) -> int

    Return index of first occurrence of v in L.
    If v is not in L return -1.

    Precondition: L is sorted and elements of L can be compared to v.

    >>>binary_search(['a','b','b','c','d'], 'b')
    1
    >>>binary_search([0,1,2,3,4,5],-2)
    -1
    """
    b = 0
    e = len(L) - 1
    
    while b <= e:
        m = len(L) // 2
        if L[m] < v:
            b = m + 1
        else:
            e = m - 1

    if b == len(L) or L[b] != v:
        return -1
    else:
        return b

Binary Search is a search algorithm that finds the specified index of a value within a sorted array
only. In effect it is like trying to find the meaning of a word in a dictionary or a description of an object in an encyclopedia.

The precondition of being sorted creates a distinct advantage that increases the speed of the search.

Let me give an example:

Imagine if you have to search a phonebook of 1,000,000 (one million) entries for the name:
"Sooham Rafiz". Since the phonebook is alphabetically arranged, you know that all the names beginning with "S" will be towards the end.

...you bisect the phonebook and see names beginning with "M",
so here 1 step has allowed us to eliminate 500,000 entries.

...you bisect again to reach "R" names, we have eliminated 250,000 entries with the
2nd step!

This is in contrast to Linear Search where 1 step eliminated 1 entry.

Hence Binary Search, by common sense is: $\mathcal{O}(log_{2}(n))$