Searching and Sorting

Prof. Dr. Mirco Schoenfeld

Recap

Last session was about data types and data structures.

Recap

Some data types…:

Tantau (2016)

Recap

…and some data structures:

Operation Arrays Lists Sets
Add item to beginning or end
Access first or last item
Access item by index
Store only unique values
Efficient test for membership

Today

Why should we care?

Motivation

Clever organization of your data will help you find things faster.

The search problem

What do we actually want to find?

Given an array containing some values,
we could search for a specific value.

The search problem

Given an array containing some values, we could search

  • a single value
  • all values
  • a single value with a certain characteristic
  • all values value with a certain characteristic

I/O

About the inputs and outputs:

We search for Inputs Outputs
a single value array + single value one array-position
all values array + single value all array-positions
a single value with a characteristic array + characteristic one array-position
all values with a characteristic array + characteristic all array-posistions

Approaches to searching

In general, there are two approaches to searching:

Linear Search

  • most basic approach
  • simply iterate over input
  • sequentially check each element
  • rarely practical

Binary Search

  • can be much faster than linear search
  • iteratively eliminates half ot the input
  • input list needs to be sorted
  • works only with random-access input

Linear Search: Implementation

Linear Search in pseudo code:

procedure linear_search (list, value)
  set i to 0
  set n to length of list
  while i < n
  do
    if (list at i) = value, terminate and return i
    increment i by 1
  done
  terminate unsuccessfully
end procedure

Linear Search: Runtime Complexity

Consider this example:

How many comparisons are needed to find

  • 27: 5
  • 4: 1
  • 8: 9

Linear Search: Runtime Complexity

How many comparisons are needed

…in the best case? \(O(1)\)
…in the worst case? \(O(n)\)
…on average? \(O(n)\)

Linear Search: Runtime Complexity

Regarding \(O(n)\) in the average case:

If each element occurs in the list once,
and each element is equally likely to be searched,
then the expected number of comparisons is

\[ \frac{ n+1 }{ 2 } \]

The O-class of that is \(O(n)\)

Linear Search: Summary

Summarizing linear search:

  • simple to implement
  • no requirements on input
  • only practical for small lists

Before Moving on: A Quick Survey

Towards binary search

Ancient storage of knowledge, usually kept on shelves