Searching algorithms

binary searching algorithm

Start
       key = 4
       get values
       set mid point
       set Imin to 0
       set Imax Len (values)-1
found = false
while found == false and Imax > = imin:
       mid=(imin=Imax)//2
IF key ==values[mid]:
       found =true
ELIF key > values[mid]:
        imin = mid + 1
    ELSE:
        imax = imid
IF found == TRUE:
    print(key,"found at pos",imid)
END IF
UNTIL found = TRUE


Time complexity
 linear search = O(n)
Binary search = O(log(n))

Binary search is more efficient , divides by 2 each time ("divide and conquer")

Disadvantages of binary searches

• The list has to be ordered
• if the values are random , the only choice is a linear search
• Binary search algorithms are harder to write (errors likely)
• if the list is short there is no point for it , (it halves the search so is good for big lists)
• if the list changes often , you will need to resort it every time
• if the items you are searching for are nearer to the front of the list there is no point in using binary search