fork download
copy 
  1. def sort(arr)
  2.     n = arr.length - 1
  3.     for i in 0..n-1
  4.         min = arr[i]
  5.         pos = i
  6.         for j in i + 1..n
  7.             if arr[j] < min
  8.                min = arr[j]
  9.                pos = j
  10.             end
  11.         end
  12.         arr[pos], arr[i] = arr[i], arr[pos]
  13.     end
  14. end
  15. def searchbin(lo, hi, key, arr)
  16.     if lo > hi
  17.        return -1
  18.     end
  19.     m = (lo + hi) >> 1
  20.     if key == arr[m]
  21.        return m
  22.     end
  23.     if key < arr[m]
  24.        return searchbin(lo, m - 1, key, arr)
  25.     else
  26.       return searchbin(m + 1, hi, key, arr)
  27.     end
  28. end
  29.  
  30. def searchBin_rec(arr, key)
  31.  
  32.     return searchbin(0, arr.length-1, key, arr)
  33.  
  34. end
  35.  
  36. def searchBin(arr, key)
  37.     n = arr.length
  38.     lo = 0
  39.     hi = n - 1
  40.     pos = -1
  41.     while lo <= hi
  42.         m = (lo + hi) >> 1
  43.         if key == arr[m]
  44.            pos = m
  45.            break
  46.         end
  47.         if key < arr[m]
  48.            hi = m - 1
  49.         else key > arr[m]
  50.           lo = m + 1
  51.         end
  52.     end
  53.     return pos
  54. end
  55. def main
  56.     arr = [1,2,3,10,20,-10,-20,2021,-2,311,310]
  57.     print arr
  58.     print "\nWhat's your key?\nkey = "
  59.     key = gets.chomp.to_i
  60.  
  61.     hash = {}
  62.     for i in 0..arr.length-1
  63.         hash[arr[i]] = i
  64.     end
  65.     sort(arr)
  66.     ans = searchBin_rec(arr, key)
  67.     if ans != -1
  68.        p "Found on position: #{hash[key]}!"
  69.     else
  70.       p "Not Found!"
  71.     end
  72. end
  73. main
  74.  
Success #stdin #stdout 0.01s 6468KB
comments (?)
stdin
copy 
311
stdout
copy 
[1, 2, 3, 10, 20, -10, -20, 2021, -2, 311, 310]
What's your key?
key = "Found on position: 9!"
https://ideone.com/yfRsGe
Binary Search Iteratively and Recursively
language:
Ruby (ruby 2.5.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!