• If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Finally, you can manage your Google Docs, uploads, and email attachments (plus Dropbox and Slack files) in one convenient place. Claim a free account, and in less than 2 minutes, Dokkio (from the makers of PBworks) can automatically organize your content for you.


Topic - Search techniques

Page history last edited by Dr. Ron Eaglin 5 years, 8 months ago

Topic - Search techniques




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(log2n). 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 )



Comments (0)

You don't have permission to comment on this page.