3.2.6 Searching Techniques

3.2.6 SEARCHING TECHNIQUES

• WHY IS EFFICIENT SEARCHING SO IMPORTANT?
• Most of the data stored by organisations is stored in Computerised Databases.  Some databases have millions of records.
• Interactive systems rely on data being retrieved from these systems quickly.
• For example : Cash Machines

• LINEAR SEARCH
• A Linear Search...
• Start at the beginning of the list.
• Compare each item in the list with the search item.
• Stop when the item is found or when the end of the list is reached.

• LINEAR SEARCH EXAMPLE
• Imagine we need to find the phone number for a student called Keith Fit in an unsorted  list of 15 students...
• We may have to access up to 15 records to find the record we need. This time it took 10 reads.

1.       Rhys                                 7788

2.       Domingo                        6545

3.       Hayden                           3987

4.       Iris                                     9009

5.       Kayla                                7886

6.       Abdul                               2345

7.       Kay                                   5843

8.       John                                 7996

9.       Sally                                  0191

10.   Keith                                6109

11.   Carla                                 7685

12.   Donna                             4243

13.   Miles                                7658

14.   Raul                                  3424

15.   Saul                                  0055

• Advantages
• This technique is very simple to code.
• A Linear Search works with an unsorted list.
• Disadvantage
• Linear Searches are slow, especially with large lists.

• BINARY SEARCH
• A Binary Search of a Sorted List...
• Find the Middle Item of the Current Search List.
• Check if the Current Item is the Search Item.
• If not then make the Current Search List either the Higher Half or the Lower Half of the list.
• Go to Step 1
• Advantage
• Much Faster than a Linear Search, especially as the List increases in size.
• 
  Calculate the Maximum Reads for a file of 1000 records..

• Disadvantages.....
• The List needs to be Sorted.
• A Binary Search is more
• Complex to Code.

and searching

• Google creates millions of indexes of web-pages.  These are lists of pages sorted by their subjects.
• Without these indexes Google would not be able to use a binary search and would not be able to return your search results so quickly. Without these indexes your search would take days!!!
• This is how it works...
• http://www.youtube.com/watch?v=BNHR6IQJGZs&feature=related

• Summary
• Efficient Searching is very important because…
• We don’t want to wait for data retrieval in ICT systems
• Large number of records to search

• Linear Search Characteristics…
• Look at each item in order
• Slow in comparison to a Binary Search
• List needs not to be sorted- simple

• Binary Search Characteristics…
• Fast in comparison to Linear Search
• Complex to code
• List has to be sorted