Binary search: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(11 intermediate revisions by the same user not shown)
Line 6: Line 6:


== Abstract view ==
== Abstract view ==
The subroutine does nothing but calling another, recursive subroutine with the same output and the following input: array <math>A</math>, element <math>s</math>, comparison <math>cmp</math> and, in addition, two indices of <math>A</math>, <math>\ell</math> and <math>r</math>, such that <math>\ell<r</math>. In the original call to this recursive subroutine, <math>\ell</math> is the first and <math>r</math> the last index of <math>A</math>.


'''Invariant:''' For every recursive call:
'''Invariant:''' For every recursive call:
# The pointer <math>p</math> points to the sequence at position <math>k_i</math>
If <math>s</math> is present at least once in <math>A</math>, then all indices of <math>A</math> where <math>s</math> is present are in the interval <math>[\ell,\ldots,r]</math>.
#The key <math>\Kappa </math> is in the range of <math>[k_i-n/2^i, k_i +n/2^i]</math>


'''Variant:''' The pointer <math>p</math> is moved so the sequence item at the position (rounded) <math>(k_i+k_{i-1})/2</math> with <math>k_0=0 if S[n/2]<\Kappa,k_0=n if S[n/2]>\Kappa  </math>
'''Variant:''' The value <math>r-\ell</math> is roughly halved in every descent in the recursion tree.


'''Break condition:''' Either <math>S[k_i]=\Kappa</math> or, otherwise, <math>k_i=k_{i+1} with S[k_i]\neq \Kappa</math>.
'''Break condition:''' Either an occurrence of <math>s</math> is found or it is <math>\ell>r</math>


== Induction basis ==  
== Induction basis ==  


'''Abstract view:''' Set <math>p:=</math> n/2.
The invariant is trivially fulfilled because <math>[\ell,\ldots,r]</math> is the entire index range of <math>A</math>.
 
'''Implementation:''' Obvious.
 
'''Proof:''' Nothing to show.


== Induction step ==
== Induction step ==


'''Abstract view:'''
# Set <math>m:=(\ell+r)/2</math>.
If p points to a node but not with key K, p descends in the appropriate direction, left or right.
# If <math>A[m]=s</math> terminate and return <math>m</math>.
'''Implementation:'''
# Otherwise, if <math>s</math> precedes <math>A[m]</math> with respect to <math>cmp</math>, apply a recursive call with <math>A</math>, <math>s</math>, <math>cmp</math>, <math>\ell</math> and<math>m-1</math>.  
 
# Otherwise, apply a recursive call with <math>A</math>, <math>s</math>, <math>cmp</math>, <math>m+1</math> and <math>r</math>.
#If <math>p.key = K</math>, terminate the algorithm and return '''''true'''''.
'''Correctness:''' obvious.
# Otherwise:
## If <math>K < p.key</math>, set <math>p </math> to the sequence element <math>k_{i+1}=k_i-n/2^i</math>.
## If <math>K > p.key</math>, set <math>p </math>to the sequence element <math>k_{i+1}=k_i-n/2^i</math>.
 
'''Correctnes:''' Obvious.


== Complexity ==
== Complexity ==


'''Statement:''' Log(n)
'''Statement:''' The asymptotic complexity is in <math>\mathcal{O}(\log n)</math>.


'''Proff:''' Obvious.
'''Proof:''' follows immediately from the variant.

Latest revision as of 06:29, 27 April 2016

Binary search

Algorithmic problem: Finding an element in a sorted array

Type of algorithm: recursion

Abstract view

The subroutine does nothing but calling another, recursive subroutine with the same output and the following input: array [math]\displaystyle{ A }[/math], element [math]\displaystyle{ s }[/math], comparison [math]\displaystyle{ cmp }[/math] and, in addition, two indices of [math]\displaystyle{ A }[/math], [math]\displaystyle{ \ell }[/math] and [math]\displaystyle{ r }[/math], such that [math]\displaystyle{ \ell\lt r }[/math]. In the original call to this recursive subroutine, [math]\displaystyle{ \ell }[/math] is the first and [math]\displaystyle{ r }[/math] the last index of [math]\displaystyle{ A }[/math].

Invariant: For every recursive call: If [math]\displaystyle{ s }[/math] is present at least once in [math]\displaystyle{ A }[/math], then all indices of [math]\displaystyle{ A }[/math] where [math]\displaystyle{ s }[/math] is present are in the interval [math]\displaystyle{ [\ell,\ldots,r] }[/math].

Variant: The value [math]\displaystyle{ r-\ell }[/math] is roughly halved in every descent in the recursion tree.

Break condition: Either an occurrence of [math]\displaystyle{ s }[/math] is found or it is [math]\displaystyle{ \ell\gt r }[/math]

Induction basis

The invariant is trivially fulfilled because [math]\displaystyle{ [\ell,\ldots,r] }[/math] is the entire index range of [math]\displaystyle{ A }[/math].

Induction step

  1. Set [math]\displaystyle{ m:=(\ell+r)/2 }[/math].
  2. If [math]\displaystyle{ A[m]=s }[/math] terminate and return [math]\displaystyle{ m }[/math].
  3. Otherwise, if [math]\displaystyle{ s }[/math] precedes [math]\displaystyle{ A[m] }[/math] with respect to [math]\displaystyle{ cmp }[/math], apply a recursive call with [math]\displaystyle{ A }[/math], [math]\displaystyle{ s }[/math], [math]\displaystyle{ cmp }[/math], [math]\displaystyle{ \ell }[/math] and[math]\displaystyle{ m-1 }[/math].
  4. Otherwise, apply a recursive call with [math]\displaystyle{ A }[/math], [math]\displaystyle{ s }[/math], [math]\displaystyle{ cmp }[/math], [math]\displaystyle{ m+1 }[/math] and [math]\displaystyle{ r }[/math].

Correctness: obvious.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(\log n) }[/math].

Proof: follows immediately from the variant.

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Binary_search&oldid=3835"