SEARCHING ON A SORTED LIST

Problem: Given a list containing
keys such that , for .
Problem is to find out if a given x is in L.

I. Use sorted property on sequential search

Quit search as soon as x is less than L[i] and declare that

Could be shown that

W(n) is still O(n).

• Jump Search
  • Jump Search (Divide and Conquer:)
  • Recursively apply partitioning in a smaller list
• RECURSIVE JUMP SEARCH: With Best Value for k
  • Binary Search: