Rosetta Code Popular

Binary Search

Locate values in a sorted array by repeatedly halving the remaining search interval.

Edit the source, then Run. Checks start after your first Run. Ctrl/⌘ + Enter runs; Tab indents. Preview services use sample data and never contact a real service.

Sourcerosettacode/popular/binary_search.vibe
def midpoint(low: int, high: int) -> int
  middle = low
  span = high - low
  step = 0

  while step < span
    step = step + 2
    if step <= span
      middle = middle + 1
    end
  end

  middle
end

def binary_search(values: array<int>, target: int, low: int, high: int) -> int | nil
  while low <= high
    middle = midpoint(low, high)
    candidate = values.fetch(middle)

    if candidate == target
      return middle
    end

    if candidate < target
      low = middle + 1
    else
      high = middle - 1
    end
  end

  nil
end

def run -> { found_first: int?, found_last: int?, found_middle: int?, missing: int? }
  values = [-31, -4, 0, 1, 5, 9, 12, 17, 23, 42, 77]
  {
    found_middle: binary_search(values, 23, 0, 10),
    found_first: binary_search(values, -31, 0, 10),
    found_last: binary_search(values, 77, 0, 10),
    missing: binary_search(values, 8, 0, 10)
  }
end

Output

Click Run example to see the result.

Code checks

Run once to load the checker. Your code stays in this browser.