Binary search: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 3: Line 3:
'''Algorithmic problem:''' [[Finding an element in a sorted array]]
'''Algorithmic problem:''' [[Finding an element in a sorted array]]


'''Prerequisites:''' The array is ascendingly sorted according to some
'''Type of algorithm:''' recursion
 
'''Type of algorithm:''' loop
 
'''Auxiliary data:''' A pointer <math>p</math> of type "pointer to list item of array lists of component type <math>\Kappa</math>".


== Abstract view ==
== Abstract view ==

Revision as of 05:54, 27 April 2016

Binary search

Algorithmic problem: Finding an element in a sorted array

Type of algorithm: recursion

Abstract view

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

  1. The pointer [math]\displaystyle{ p }[/math] points to the sequence at position [math]\displaystyle{ k_i }[/math]
  2. The key [math]\displaystyle{ \Kappa }[/math] is in the range of [math]\displaystyle{ [k_i-n/2^i, k_i +n/2^i] }[/math]

Variant: The pointer [math]\displaystyle{ p }[/math] is moved so the sequence item at the position (rounded) [math]\displaystyle{ (k_i+k_{i-1})/2 }[/math] with [math]\displaystyle{ k_0=0 if S[n/2]\lt \Kappa,k_0=n if S[n/2]\gt \Kappa }[/math]

Break condition: Either [math]\displaystyle{ S[k_i]=\Kappa }[/math] or, otherwise, [math]\displaystyle{ k_i=k_{i+1} with S[k_i]\neq \Kappa }[/math].

Induction basis

Abstract view: Set [math]\displaystyle{ p:= }[/math] n/2.

Implementation: Obvious.

Proof: Nothing to show.

Induction step

Abstract view:

If p points to a node but not with key K, p descends in the appropriate direction, left or right.

Implementation:

  1. If [math]\displaystyle{ p.key = K }[/math], terminate the algorithm and return true.
  2. Otherwise:
    1. If [math]\displaystyle{ K \lt p.key }[/math], set [math]\displaystyle{ p }[/math] to the sequence element [math]\displaystyle{ k_{i+1}=k_i-n/2^i }[/math].
    2. If [math]\displaystyle{ K \gt p.key }[/math], set [math]\displaystyle{ p }[/math]to the sequence element [math]\displaystyle{ k_{i+1}=k_i-n/2^i }[/math].

Correctnes: Obvious.

Complexity

Statement: Log(n)

Proff: Obvious.