[DSA] searching

Have you ever tried to find something in your house/room. Yet can't seems to ever find it. Now, lets not talk about misplacing items out of carelessness. Let's discuss how to "find" items in your wardrobe.

Assume you have your apparels hanging in the wardrobe, how would you "find" your favorite shirt/dress? would you start looking from the left hand side? the right hand side or simply in the middle???

If you find 1 apparel at a time from either direction, that is linear search. The worst case scenario is, you would traverse all your apparels before finding your favourite.

If you have sorted your apparels according to a certain sequence, eg, warm colours to the right and cold colours to the left, you can simply start finding from the middle, then to the left if your favourite falls in the cold colour. This is binary search. searching time can be reduced significantly.

Again, if you do like what i did, simply pile up all my apparels in the wardrobe without sorting/folding/ironing it. "Finding" for a particular item in the wardrobe can be disastrous.

Linear Search => O(N)

Go through the entire array of items to lookup on the searched key. The sequence of items are not sorted.

Best case , the 1st item in the array.

Worst case, the last item in the array.

Average case, traverse for half of the array

Binary Search => O(logN)

Uses a divide and conquer method.

array of items must be sorted first, involves a cost.

L <> root

|---|---|

L---M---R

For any array of 1000000 items, Linear search need 500000 comparison (assume an average case), Binary Search 20 comparison.

Pop Quiz

1. Create a generic code of linear search to take in different data type.

2. Create a Binary Search tht uses recursive method.

3. Use find() or search() from the STL to do a lookup of a string, among many strings stored in the memory