• Pseudocode for binary search
• Source

What follows is annotated pseudocode for a binary search over a sorted array of real numbers. Note that this—like virtually all pseudocode expressions (or programming language code expressions, for that matter) of a non-trivial procedure—is just one of many ways to express the binary search algorithm.

Pseudocode for binary search

Symbols

Beyond the basic arithmetic and logical operations, this pseudocode uses the following mathematical symbol:

Symbol	Meaning
$\lfloor x \rfloor$	The floor of a real number $x$—i.e., the largest integer that is less than or equal to $x$.

Given

• $D\text{: real array}$, of length $n$, to be searched: $D = (d_0, d_1, \ldots, d_{n - 1})$.

• The elements of $D$ are in ascending order.

• $v\text{: real}$ is the value to search for:

  • If $v$ is in $D$, its position must be returned.
  • If $v$ is not in $D$, $-(p + 1)$ must be returned, where insertion of $v$ at position $p$ would preserve the sort order.

To search for $v$ in $D$

1. $a\text{: integer} \gets 0$.

   ($a$ is the lower inclusive bound of the search range.)

2. $b\text{: integer} \gets n$.

   ($b$ is the upper exclusive bound of the search range.)

3. While $a < b$:

   1. $m\text{: integer} \gets \left \lfloor \frac{a + b}{2} \right \rfloor$.

      ($m$ is the midpoint of the search range.)

   2. If $d_m = v$,

      • return $m$;

        (Done: $v$ is found at position $m$.)

      otherwise, if $d_m > v$,

      • $b \gets m$;

        ($d_m$ is too high, so $m$ is used as the new exclusive upper bound of the search range.)

      otherwise,

      • $a \gets m + 1$.

        ($d_m$ is too low, so $(m + 1)$ is used as the new inclusive lower bound of the search range.)

4. Return $-(a + 1)$.

   ($v$ is not in $D$, but inserting $v$ at position $a$ would preserve the sorted order.)

Source

### Symbols

Beyond the basic arithmetic and logical operations, this pseudocode uses the following mathematical symbol:

| Symbol | Meaning |
|:------:|:--------|
| $\lfloor x \rfloor$ | The _floor_ of a real number $x$---i.e., the largest integer that is less than or equal to $x$. |

### Given

* $D\text{: real array}$, of length $n$, to be searched: $D = (d_0, d_1, \ldots, d_{n - 1})$.

* The elements of $D$ are in ascending order.
    
* $v\text{: real}$ is the value to search for: 

    * If $v$ is in $D$, its position must be returned. 
    * If $v$ is _not_ in $D$, $-(p + 1)$ must be returned, where insertion of $v$ at position $p$ would preserve the ascending sort order.

### To search for $v$ in $D$

1. $a\text{: integer} \gets 0$. 

    ($a$ is the lower _inclusive_ bound of the search range.)

2. $b\text{: integer} \gets n$. 
    
    ($b$ is the upper _exclusive_ bound of the search range.)

3. While $a < b$:

    1. $m\text{: integer} \gets \left \lfloor \frac{a + b}{2} \right \rfloor$. 
    
        ($m$ is the midpoint of the search range.)
    
    2. If $d_m = v$,
   
        * return $m$;
        
            (Done: $v$ is found at position $m$.)
        
        otherwise, if $d_m > v$,
        
        * $b \gets m$;
        
            ($d_m$ is too high, so $m$ is used as the new exclusive upper bound of the search range.)
        
        otherwise,
        
        * $a \gets m + 1$.
        
            ($d_m$ is too low, so $(m + 1)$ is used as the new inclusive lower bound of the search range.)
        
4. Return $-(a + 1)$.

    ($v$ is not in $D$, but inserting $v$ at position $a$ would preserve the sorted order.)