Topic 6 – Search techniques

Introduction

One of the great things about computers is the ability to search very quickly. This is part because the computer can perform very mundane chores rapidly, but when the searching gets into the billions, trillions, and beyond – you need more than just brute force. You will want to know how searching algorithms work – and then get an understanding of sorting and hashing – all the techniques used to speed that searching up.

Search Algorithms

There are so many different search algorithms that they have their own category in wikipedia ( http://en.wikipedia.org/wiki/Category:Search_algorithms ). We are going to look at some of them now, and then return to this topic after you have covered some more advanced data structures that also greatly increase your ability to search.

Linear Search

The simplest search algorithm is linear or sequential search. You simply search every element in an array – http://en.wikipedia.org/wiki/Linear_search The Wikipedia article contains some nuances of linear search including use of sentinel values, recursive techniques, and implementations.

Binary Search

Ever used a phone book? When looking up numbers you typically either turn to the middle of the book or open it to where you think you are most likely to find the number – then you flip pages starting with a lot, finally getting to a few. This is possible because the phone book has already sorted the items that you are searching. If the items you are searching are sorted then the maximum time complexity is O(log₂n). The classic algorithms for a binary search are iterative and recursive. You will need to be familiar with both – they are well documented at http://en.wikipedia.org/wiki/Binary_search_algorithm . Coding the binary search is a very good exercise and is surprisingly tricky. I recommend practice with the algorithm as it is easy to test and is also a great test of your coding and algorithm skills. (See also http://en.wikipedia.org/wiki/Interpolation_search )