Page 264 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 14: Searching

{ Notes
// if the dwMidpoint is not the target adjust the
range accordingly
if (target < searchspace[dwMidpoint])
{
dwLast = dwMidpoint - 1;
}
else
{
dwFirst = dwMidpoint + 1;
}
}

// Return value

if (fFound)
{
return(dwMidpoint);
}
else
{
return(NOTFOUND);
}
}
}

Task Compare and contrast Linear search and Binary search.
Self Assessment

State whether the following statements are true or false:
9. A linear search selects the median (middle) element in the array and compares its value to
that of the target value.
10. Every iteration eliminates half of the remaining possibilities.
11. Binary search requires a sorted collection.
12. A binary search on an array is O(log n).
13. For very small arrays a binary search can prove faster than a linear search.

14. The binary search assumes easy random-access to the data space it is searching.
15. Once the data is sorted it can also prove very expensive to add or delete items.

LOVELY PROFESSIONAL UNIVERSITY 257