Linear Search v/s Bisection (Binary) Search

Linear Search:

• It is a sequential search over a list.
• A simple searching technique.
• Used when elements in the list are Unsorted. 
• Its not efficient. (Efficiency discussed below) 

Explanation:

• Say we have a list [4, 8, 45, 24, 10, 32, 9, 56]
• We are searching for 32.
• In Linear Search we'll go through all the elements of the list & compare if its equal to 32
• If not, then proceed to next element, else if yes then return the position of 32.

def linear(n):
     s = [4,8,45,24,10,32,9,56]
     iterations = 0
     for i in s:
          iterations += 1
          if i == n:
               print 'iterations','=',str(iterations)
               return
     print str(n),'not found'

Output:
>>> linear(32)
iterations = 6 #compare with the iterations of Bisection Search
>>> linear(22)
22 not found

Bisection (Binary) Search:

• Used when list is Sorted.
• A more efficient way of Searching

Explanation:

• Say we have a list [4, 8, 9, 10, 24, 32, 45, 56]
• We are searching for 32.
• Divide list in two halves, & compare 32 with the middle element
• 32>25, therefore neglect first half, i.e. our list becomes [4, 8, 9, 10, 24, 32, 45, 56]
• Now our list is [32, 45, 56]
• Compare 32 again with middle element, 32 < 45
• So list becomes  [32, 45, 56]
• [32] is our list now, 32 = 32.
• Hence 32 found

def bisection(n):
     s = [4,8,9,10,24,32,45,56]
     iterations = 0
     low = 0
     high = len(s)-1
     ans = (high + low)/2
     iterations += 1 #because we've already divided list in half at this point
     while s[ans] != n:
         if  s[ans] < n:
             low = ans + 1
         else:
             high = ans
         ans = (high + low)/2
         iterations += 1 
     print 'iterations = ',str(iterations)

Output:
>>> bisection(32)
iterations =  2  #compare with the iterations of Linear Search

Points to note between Linear Search & Bisection Search:

• Note that we cut down the list in half each time we compare 32 with any element, while in Linear Search we kept on searching through whole list.
• Hence Bisection Search is way better than Linear Search.
• There is technical term to say this, 'Complexity', & represented as O()
• Complexity of Linear Search is O(n), where n is the number of elements in the list.
• Complexity of Bisection Search is O(log n)

Note:
This is a part of what I learn in an online Open Course Ware offered by MIT on edX
Its for my personal reference & also for those who have missed the course.
You too can enroll yourself on edX (if they are still offering the course MITx 6.00x)