Divide and conquer (Binary search in Ruby)

binary_search_in_ruby.md

Binary Search

Problem Introduction

In this problem, you will implement the binary search algorithm that allows searching very efficiently (even huge) lists, provided that the list is sorted.

Problem Description

Task.

The goal in this code problem is to implement the binary search algorithm.

Input Format.

The first line of the input contains an integer 𝑛 and a sequence 𝑎0 < 𝑎1 < . . . < 𝑎𝑛−1 of 𝑛 pairwise distinct positive integers in increasing order. The next line contains an integer 𝑘 and 𝑘 positive integers 𝑏0, 𝑏1, . . . , 𝑏𝑘−1.

Constraints.

1 ≤ 𝑘 ≤ 105; 1 ≤ 𝑛 ≤ 3 · 104; 1 ≤ 𝑎𝑖 ≤ 109 for all 0 ≤ 𝑖 < 𝑛; 1 ≤ 𝑏𝑗 ≤ 109 for all 0 ≤ 𝑗 < 𝑘;

Output Format.

For all 𝑖 from 0 to 𝑘 − 1, output an index 0 ≤ 𝑗 ≤ 𝑛 − 1 such that 𝑎𝑗 = 𝑏𝑖 or −1 if there is no such index.

Example

• Input:

5 1 5 8 12 13
5 8 1 23 1 11

• Output:

2 0 -1 0 -1

In this sample, we are given an increasing sequence 𝑎0 = 1, 𝑎1 = 5, 𝑎2 = 8, 𝑎3 = 12, 𝑎4 = 13 of length five and five keys to search: 8, 1, 23, 1, 11. We see that 𝑎2 = 8 and 𝑎0 = 1, but the keys 23 and 11 do not appear in the sequence 𝑎. For this reason, we output a sequence 2, 0,−1, 0,−1.

def find_index(array, number)
  first_index = 0
  last_index  = array.length - 1

  while first_index <= last_index
    mid_index = (first_index + last_index) / 2
    array_el  = array[mid_index].to_i

    if array_el == number
      return mid_index
    elsif array_el > number
      last_index = mid_index - 1
      return -1 if first_index > last_index
    elsif array_el < number
      first_index = mid_index + 1
      return -1 if first_index > last_index
    end
  end
end

sorted_array = gets.chomp.split
sorted_array.shift
numbers = gets.chomp.split
numbers.shift

indexes = numbers.map do |number|
  find_index(sorted_array, number.to_i)
end

indexes.each do |el|
  print el.to_s + " "
end