CIS 150 Searching

• Search through an array
• Explain the differences between linear and binary searching

• For the following, assume n is the number of items in the array.
• Linear (sequential) search
  • Linear searches look at one element after another starting with the first element.
  • The array does not have to be sorted to perform a linear search.
  • Average comparisons if item exists is n/2
  • For n = 1,000,000: average comparisons is 500,000
  • Average comparisons if item does not exist and data is sorted is n/2
  • If item does not exist and data is not sorted, then n comparisons are done.
• Binary search
  • Data must be in sorted order.
  • Binary search discards half of the search domain after each comparison.
  • The average number of comparisons is log₂n - 1
  • For n = 1,000,000: average comparisons is 19 or less (over 26,000 times faster than linear)
• 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

int linsearch(int k, int arr[], int len) { for (int i=0; i<len; i++) { if (k == arr[i]) return i; } return -1; }

int binsearch(int k, int arr[], int len) { int hi = len - 1; int lo = 0; int middle; while (hi >= lo) { middle = (hi + lo) / 2; if (arr[middle] == k) return middle; else if (arr[middle] > k) hi = middle - 1; else lo = middle + 1; } return -1; }