Binary Search

Challenge Overview

Implement a binary search algorithm.

Visit the binary-search exercise on Exercism to read the full instructions and download the exercise files.

Community Solutions

View Community Solutions

The following are the top 3 community solutions by stars:

Solution 1 by @glennj (⭐ 0) — View on Exercism
Solution 2 by @keiraville (⭐ 0) — View on Exercism
Solution 3 by @hl4 (⭐ 0) — View on Exercism

Source: Exercism sml/binary-search

💡 View Solution

fun find (haystack: int array, needle: int): int =
  let fun find' left right =
        if left > right then raise Fail "value not in array"
        else let val mid  = (left + right) div 2
                 val elem = Array.sub (haystack, mid)
             in  if      needle < elem then find' left (mid - 1)
                 else if needle > elem then find' (mid + 1) right
                 else mid
             end
  in  find' 0 (Array.length haystack - 1)