A binary search divides a range of values into halves, and continues to narrow down the field of search until the unknown value is found. It is the classic example of a "divide and conquer" algorithm.

As an analogy, consider the children's game "guess a number." The scorer has a secret number, and will only tell the player if their guessed number is higher than, lower than, or equal to the secret number. The player then uses this information to guess a new number.

As the player, an optimal strategy for the general case is to start by choosing the range's midpoint as the guess, and then asking whether the guess was higher, lower, or equal to the secret number. If the guess was too high, one would select the point exactly between the range midpoint and the beginning of the range. If the original guess was too low, one would ask about the point exactly between the range midpoint and the end of the range. This process repeats until one has reached the secret number.



Task

Given the starting point of a range, the ending point of a range, and the "secret value", implement a binary search through a sorted integer array for a certain number. Implementations can be recursive or iterative (both if you can). Print out whether or not the number was in the array afterwards. If it was, print the index also.

There are several binary search algorithms commonly seen. They differ by how they treat multiple values equal to the given value, and whether they indicate whether the element was found or not. For completeness we will present pseudocode for all of them.

All of the following code examples use an "inclusive" upper bound (i.e. high = N-1 initially). Any of the examples can be converted into an equivalent example using "exclusive" upper bound (i.e. high = N initially) by making the following simple changes (which simply increase high by 1):

 change high = N-1 to high = N
 change high = mid-1 to high = mid
 (for recursive algorithm) change if (high < low) to if (high <= low)
 (for iterative algorithm) change while (low <= high) to while (low < high)
Traditional algorithm
The algorithms are as follows (from Wikipedia). The algorithms return the index of some element that equals the given value (if there are multiple such elements, it returns some arbitrary one). It is also possible, when the element is not found, to return the "insertion point" for it (the index that the value would have if it were inserted into the array).

Recursive Pseudocode:

  // initially called with low = 0, high = N-1
  BinarySearch(A[0..N-1], value, low, high) {
      // invariants: value > A[i] for all i < low
                     value < A[i] for all i > high
      if (high < low)
          return not_found // value would be inserted at index "low"
      mid = (low + high) / 2
      if (A[mid] > value)
          return BinarySearch(A, value, low, mid-1)
      else if (A[mid] < value)
          return BinarySearch(A, value, mid+1, high)
      else
          return mid
  }

Iterative Pseudocode:

  BinarySearch(A[0..N-1], value) {
      low = 0
      high = N - 1
      while (low <= high) {
          // invariants: value > A[i] for all i < low
                         value < A[i] for all i > high
          mid = (low + high) / 2
          if (A[mid] > value)
              high = mid - 1
          else if (A[mid] < value)
              low = mid + 1
          else
              return mid
      }
      return not_found // value would be inserted at index "low"
  }

Leftmost insertion point
The following algorithms return the leftmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the lower (inclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than or equal to the given value (since if it were any lower, it would violate the ordering), or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level.

Recursive Pseudocode:

  // initially called with low = 0, high = N - 1
  BinarySearch_Left(A[0..N-1], value, low, high) {
      // invariants: value > A[i] for all i < low
                     value <= A[i] for all i > high
      if (high < low)
          return low
      mid = (low + high) / 2
      if (A[mid] >= value)
          return BinarySearch_Left(A, value, low, mid-1)
      else
          return BinarySearch_Left(A, value, mid+1, high)
  }

Iterative Pseudocode:

  BinarySearch_Left(A[0..N-1], value) {
      low = 0
      high = N - 1
      while (low <= high) {
          // invariants: value > A[i] for all i < low
                         value <= A[i] for all i > high
          mid = (low + high) / 2
          if (A[mid] >= value)
              high = mid - 1
          else
              low = mid + 1
      }
      return low
  }

Rightmost insertion point
The following algorithms return the rightmost place where the given element can be correctly inserted (and still maintain the sorted order). This is the upper (exclusive) bound of the range of elements that are equal to the given value (if any). Equivalently, this is the lowest index where the element is greater than the given value, or 1 past the last index if such an element does not exist. This algorithm does not determine if the element is actually found. This algorithm only requires one comparison per level. Note that these algorithms are almost exactly the same as the leftmost-insertion-point algorithms, except for how the inequality treats equal values.

Recursive Pseudocode:

  // initially called with low = 0, high = N - 1
  BinarySearch_Right(A[0..N-1], value, low, high) {
      // invariants: value >= A[i] for all i < low
                     value < A[i] for all i > high
      if (high < low)
          return low
      mid = (low + high) / 2
      if (A[mid] > value)
          return BinarySearch_Right(A, value, low, mid-1)
      else
          return BinarySearch_Right(A, value, mid+1, high)
  }

Iterative Pseudocode:

  BinarySearch_Right(A[0..N-1], value) {
      low = 0
      high = N - 1
      while (low <= high) {
          // invariants: value >= A[i] for all i < low
                         value < A[i] for all i > high
          mid = (low + high) / 2
          if (A[mid] > value)
              high = mid - 1
          else
              low = mid + 1
      }
      return low
  }

Extra credit
Make sure it does not have overflow bugs.

The line in the pseudo-code above to calculate the mean of two integers:

mid = (low + high) / 2
could produce the wrong result in some programming languages when used with a bounded integer type, if the addition causes an overflow. (This can occur if the array size is greater than half the maximum integer value.) If signed integers are used, and low + high overflows, it becomes a negative number, and dividing by 2 will still result in a negative number. Indexing an array with a negative number could produce an out-of-bounds exception, or other undefined behavior. If unsigned integers are used, an overflow will result in losing the largest bit, which will produce the wrong result.

One way to fix it is to manually add half the range to the low number:

mid = low + (high - low) / 2
Even though this is mathematically equivalent to the above, it is not susceptible to overflow.

Another way for signed integers, possibly faster, is the following:

mid = (low + high) >>> 1
where  >>>  is the logical right shift operator. The reason why this works is that, for signed integers, even though it overflows, when viewed as an unsigned number, the value is still the correct sum. To divide an unsigned number by 2, simply do a logical right shift.



Related task

 Guess the number/With Feedback (Player)


See also

 wp:Binary search algorithm
 Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken.


 
 
/* ARM assembly Raspberry PI  */
/*  program binsearch.s   */
 
/************************************/
/* Constantes                       */
/************************************/
.equ STDOUT, 1     @ Linux output console
.equ EXIT,   1     @ Linux syscall
.equ WRITE,  4     @ Linux syscall
/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:        .ascii "Value find at index : "
sMessValeur:        .fill 11, 1, ' '            @ size => 11
szCarriageReturn:   .asciz "\n"
sMessRecursif:      .asciz "Recursive search : \n"
sMessNotFound:      .asciz "Value not found. \n"
 
.equ NBELEMENTS,      9
TableNumber:	     .int   4,6,7,10,11,15,22,30,35
 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                                           @ entry of program 
    mov r0,#4                                   @ search first value
    ldr r1,iAdrTableNumber                      @ address number table
    mov r2,#NBELEMENTS                          @ number of élements 
    bl bSearch
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
 
    mov r0,#11                                  @ search median value
    ldr r1,iAdrTableNumber
    mov r2,#NBELEMENTS
    bl bSearch
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
 
    mov r0,#12                                  @value not found
    ldr r1,iAdrTableNumber
    mov r2,#NBELEMENTS
    bl bSearch
    cmp r0,#-1
    bne 2f
    ldr r0,iAdrsMessNotFound
    bl affichageMess 
    b 3f
2:
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
3:
    mov r0,#35                                  @ search last value
    ldr r1,iAdrTableNumber
    mov r2,#NBELEMENTS
    bl bSearch
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
/****************************************/
/*       recursive                      */
/****************************************/
    ldr r0,iAdrsMessRecursif
    bl affichageMess                            @ display message
 
    mov r0,#4                                   @ search first value
    ldr r1,iAdrTableNumber
    mov r2,#0                                   @ low index of elements
    mov r3,#NBELEMENTS - 1                      @ high index of elements
    bl bSearchR
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
 
    mov r0,#11
    ldr r1,iAdrTableNumber
    mov r2,#0
    mov r3,#NBELEMENTS - 1
    bl bSearchR
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
 
    mov r0,#12
    ldr r1,iAdrTableNumber
    mov r2,#0
    mov r3,#NBELEMENTS - 1
    bl bSearchR
    cmp r0,#-1
    bne 2f
    ldr r0,iAdrsMessNotFound
    bl affichageMess 
    b 3f
2:
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
3:
    mov r0,#35
    ldr r1,iAdrTableNumber
    mov r2,#0
    mov r3,#NBELEMENTS - 1
    bl bSearchR
    ldr r1,iAdrsMessValeur                      @ display value
    bl conversion10                             @ call function
    ldr r0,iAdrsMessResult
    bl affichageMess                            @ display message
 
100:                                            @ standard end of the program 
    mov r0, #0                                  @ return code
    mov r7, #EXIT                               @ request to exit program
    svc #0                                      @ perform the system call
 
iAdrsMessValeur:          .int sMessValeur
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsMessResult:          .int sMessResult
iAdrsMessRecursif:        .int sMessRecursif
iAdrsMessNotFound:        .int sMessNotFound
iAdrTableNumber:          .int TableNumber
 
/******************************************************************/
/*     binary search   iterative                                  */ 
/******************************************************************/
/* r0 contains the value to search */
/* r1 contains the adress of table */
/* r2 contains the number of elements */
/* r0 return index or -1 if not find */
bSearch:
    push {r2-r5,lr}                                 @ save registers
    mov r3,#0                                       @ low index
    sub r4,r2,#1                                    @ high index = number of elements - 1
1:
    cmp r3,r4
    movgt r0,#-1                                    @not found
    bgt 100f
    add r2,r3,r4                                    @ compute (low + high) /2
    lsr r2,#1
    ldr r5,[r1,r2,lsl #2]                           @ load value of table at index r2
    cmp r5,r0
    moveq r0,r2                                     @ find !!!
    beq 100f
    addlt r3,r2,#1                                  @ lower -> index low = index + 1
    subgt r4,r2,#1                                  @ bigger -> index high = index - 1
    b 1b                                            @ and loop
100:
    pop {r2-r5,lr}
    bx lr                       @ return 
/******************************************************************/
/*     binary search   recursif                                  */ 
/******************************************************************/
/* r0 contains the value to search */
/* r1 contains the adress of table */
/* r2 contains the low index of elements */
/* r3 contains the high index of elements */
/* r0 return index or -1 if not find */
bSearchR:
    push {r2-r5,lr}                                  @ save registers
    cmp r3,r2                                        @ index high < low ?
    movlt r0,#-1                                     @ yes -> not found
    blt 100f
 
    add r4,r2,r3                                     @ compute (low + high) /2
    lsr r4,#1
    ldr r5,[r1,r4,lsl #2]                            @ load value of table at index r4
    cmp r5,r0
    moveq r0,r4                                      @ find !!!
    beq 100f 
 
    bgt 1f                                           @ bigger ?
    add r2,r4,#1                                     @ no new search with low = index + 1
    bl bSearchR
    b 100f
1:                                                   @ bigger
    sub r3,r4,#1                                     @ new search with high = index - 1
    bl bSearchR
100:
    pop {r2-r5,lr}
    bx lr                                            @ return 
/******************************************************************/
/*     display text with size calculation                         */ 
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
    push {r0,r1,r2,r7,lr}                          @ save  registres
    mov r2,#0                                      @ counter length 
1:                                                 @ loop length calculation 
    ldrb r1,[r0,r2]                                @ read octet start position + index 
    cmp r1,#0                                      @ if 0 its over 
    addne r2,r2,#1                                 @ else add 1 in the length 
    bne 1b                                         @ and loop 
                                                   @ so here r2 contains the length of the message 
    mov r1,r0                                      @ address message in r1 
    mov r0,#STDOUT                                 @ code to write to the standard output Linux 
    mov r7, #WRITE                                 @ code call system "write" 
    svc #0                                         @ call systeme 
    pop {r0,r1,r2,r7,lr}                           @ restaur des  2 registres
    bx lr                                          @ return  
/******************************************************************/
/*     Converting a register to a decimal unsigned                */ 
/******************************************************************/
/* r0 contains value and r1 address area   */
/* r0 return size of result (no zero final in area) */
/* area size => 11 bytes          */
.equ LGZONECAL,   10
conversion10:
    push {r1-r4,lr}                                 @ save registers 
    mov r3,r1
    mov r2,#LGZONECAL
 
1:	                                            @ start loop
    bl divisionpar10U                               @unsigned  r0 <- dividende. quotient ->r0 reste -> r1
    add r1,#48                                      @ digit
    strb r1,[r3,r2]                                 @ store digit on area
    cmp r0,#0                                       @ stop if quotient = 0 
    subne r2,#1                                     @ else previous position
    bne 1b	                                    @ and loop
                                                    @ and move digit from left of area
    mov r4,#0
2:
    ldrb r1,[r3,r2]
    strb r1,[r3,r4]
    add r2,#1
    add r4,#1
    cmp r2,#LGZONECAL
    ble 2b
                                                     @ and move spaces in end on area
    mov r0,r4                                        @ result length 
    mov r1,#' '                                      @ space
3:
    strb r1,[r3,r4]                                  @ store space in area
    add r4,#1                                        @ next position
    cmp r4,#LGZONECAL
    ble 3b                                           @ loop if r4 <= area size
 
100:
    pop {r1-r4,lr}                                   @ restaur registres 
    bx lr                                            @return
 
/***************************************************/
/*   division par 10   unsigned                    */
/***************************************************/
/* r0 dividende   */
/* r0 quotient */	
/* r1 remainder  */
divisionpar10U:
    push {r2,r3,r4, lr}
    mov r4,r0                                        @ save value
    //mov r3,#0xCCCD                                 @ r3 <- magic_number lower  raspberry 3
    //movt r3,#0xCCCC                                @ r3 <- magic_number higter raspberry 3
    ldr r3,iMagicNumber                              @ r3 <- magic_number    raspberry 1 2
    umull r1, r2, r3, r0                             @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0) 
    mov r0, r2, LSR #3                               @ r2 <- r2 >> shift 3
    add r2,r0,r0, lsl #2                             @ r2 <- r0 * 5 
    sub r1,r4,r2, lsl #1                             @ r1 <- r4 - (r2 * 2)  = r4 - (r0 * 10)
    pop {r2,r3,r4,lr}
    bx lr                                            @ leave function 
iMagicNumber:  	.int 0xCCCCCCCD
 
 