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))$

Searching algorithms Part 1.

This is the entry for Week 7 and Week 8.

This week t'was a good week, because I finally saw some beautiful code on my lecture slide.

My eyes teared up when I finally saw this piece of beautiful code.

The code above shows a linear search algorithm.  But what is Linear Search anyway?

Let me explain in layman's terms:

Imagine that you have a stack of cards and you want to find a card with a certain rank, for example "Jack", how would you implement that method of search?

Say, you also have gun to your head so that you would search fas.. yeah
I believe I'm overthinking this hypothetical scenario.

How would you do it?

Answer: (Most probably) go through each card one-by-one searching for a Jack.

Me: Hooray! You can do Linear Search!

Linear Search is the most obvious search algorithm: going through a list or array one element at a time, in order. It isn't terribly efficient either...

Given that the course has finally covered enough logical material to cover an algorithm, we have also covered enough material to develop a tool to analyze the algorithm.
That tool is called big-Oh

Big-Oh effectively catalogues functions by their rate of growth.
I personally though such a concept is effective, as it allows us to distinguish functions of different growth rates.

Consider the functions:

$2n^2$, $12n^2 + 100$, $10^6n^2 + 10^{6^6}$

despite the large variance in the coefficients of the functions above, we can prove that
there is a certain point of $n$ beyond which a multiple of the function $n^2$ will out-grow all the functions above.

Hence we say these functions are in $\mathcal{O}(n^2)$

In mathematical presentation $\mathcal{O}(n^2)$ is represented as:

$\mathcal{O}(n^2) = \{f:\mathbb{N}\Rightarrow \mathbb{R}^{\geq 0} | \exists c \in \mathbb{R^+}, \exists B \in \mathbb{N}, \forall n \in \mathbb{N}, n\geq B \Rightarrow f(n) \leq cn^2 \}$

Phew! A lot of notation.

Initially, I found the idea of big-Oh to be absurd, as I found it hard to swallow the fact that even extremely small coefficient quadratic equations and extremely

large coefficient quadratics fit in the

same big Oh, surely $1000000000x^2$ grows faster than $x^2$?

I will talk more about big-Oh in the next post...