CIS 250 - Searching

Objectives

• searching through arrays

Array searching

• linear (sequential) search
  • searches one element after another from beginning
  • no sort order needed
  • average comparisons if item exists is n/2
  • average comparisons if item doesn't exist and data sorted is n/2
  • n checks made if item doesn't exist and data not sorted
• binary search
  • discards half of search domain each check
  • data must be in sorted order
  • average comparisons is log₂n - 1
• see search.cpp for a linear/binary search comparison
• take note that in the sample program, binary search is so much faster than linear search that binary search can take time out to sort the array and still be faster than linear search when conducting many searches
• comparison
  • 10 items: linear = 5 comparisons, binary = 2.3 comparisons
  • 100 items: linear = 50 comparisons, binary = 5.6 comparisons
  • 1000 items: linear = 500 comparisons, binary = 9 comparisons
  • 10000 items: linear = 5000 comparisons, binary = 12.3 comparisons
  • 100000 items: linear = 50000 comparisons, binary = 15.6 comparisons