Searching

Searching involves determining whether a given value is in a list

Linear search

A linear search is a search method which works on any linear list

Algorithm for linear search of list in array

Input: search value, array to be searched (including number of items)
Output: indication of whether value is found

begin
while not end of list and search item not found
    Go to next item of list.
if item found
    Return "successful"; .
else
    Return "not successful";
end

C++ translation

int search (int sval, int a[], int size) {
int sindex = 0;
while (sindex < size && sval != a[sindex])
sindex++;
return (sindex != size);
}

Binary search

Introduction

The array MUST BE SORTED!

Example

Index	1	2	3	4	5	6	7	8	9	10	11
Value	12	15	17	25	48	59	67	79	81	88	99

Algorithm (iterative version)

Input: search value, array to be searched (including number of items)
Output: indication of whether value is found

begin
low = minindex;
high = maxindex;
do
    Calculate midpoint between low and high.
    if search value < value at midpoint
      high = midpoint - 1
    else
      if search value > value at midpoint
        low = midpoint + 1
while (low <= high and search value != value at midpoint)
if (low > high)
    Return "not successful".
else
    Return "successful".
end

Comparison of linear vs. binary search for list of n items

list not ordered

	Linear Search
Worst Case	n
Average Case	n/2

list ordered

	Linear Search	Binary Search
Worst Case	n	n
Average Case	n/2	better than log n

Recursion

A function may call itself rather than looping

Advantage: may save programming time

Algorithm (recursive version)

Input: search value, array to be searched (including number of items) low and high (bounds for search)
Output: indication of whether value is found

begin
if (low <= high)
    Calculate midpoint between low and high.
    if search value < value at midpoint
     Search lower part of array.
    else
      if search value > value at midpoint
        Search upper part of array.
      else
        Return "successful".
else
    Return "not successful".
end

C++ version

int search (int sval, int a[], int low, int high) {
if (low <= high) {
    midpt = (low + high)/2;
    if (sval < a[midpt])
      search (sval, a, low, midpt-1);
    else
      if (sval > a[midpt])
        search (sval, a, midpt+1, high);
      else
        return 1;
    return 0;
}
}

Recursion in general

	A recursive function almost never contains a loop. (It calls itself rather than looping.)
	To write a recursive function Decide on the stopping condition(s).. Write the code for the stopping condition(s). Write the code for the continuing condition(s).

Run-time efficiency vs. programmer time efficiency