Magic Indices Algorithm

Aug 8, 2016

This week's post will be a bit shorter than usual as VCS has kept us neck deep in new material. So without further ado, let's get into it.

The Problem

Considering a simple array, a magic index can be described as the index that matches its own value. For instance given the array

  [-3, -2, 1, 3, 5]

3 would be the magic index because it matches its corresponding value in the array.

The problem is thus. Given a sorted array of distinct integers, write a method to find a magic index if one exists, otherwise return false.

Anyone with a week's worth of coding under the belt could get this right away. They might answer with something like this.

  def find_magic_index(arr)
    arr.each_with_index { |v,i| return v if v == i}
    false
  end

Fair enough, it doesn't get much simpler than that. So how about if I said that your solution must come in at under O(n) time complexity? As we can see above, this first solution does not meet that requirement, as it is just at O(n). So how can we improve?

If you remember your fundamentals and that our input array is *distinct and sorted*, this additional constraint shouldn't prove to be too much of a challenge. Think searches, probably the very first one you ever learned.

If you guessed binary sort, you guessed correctly! Here's what just such a solution might look like.

  def binary_find_magic_index(arr)
    first = 0
    sec   = arr.length - 1
    loop do
      mid = first + (arr[first..sec].length / 2)
      if arr[mid] == mid
        return mid
      elsif first == sec - 1
        return first if arr[first] == first
        return sec   if arr[sec] == sec
        break
      elsif arr[mid] > mid
        sec = mid
      elsif arr[mid] < mid
        first = mid
      end
    end
    false
  end

This works largely because of the explicit conditions stated in the initial description of the problem, namely the parts constraining the input array to distinct, sequential numbers. Because of these constraints, we can confidently say that any index whose value is greater than its cooresponding array element must be less than the magic index if one exists. This is because the indexing happens at a constant rate of one, while that rate is the slowest the values will ever increase (or decrease) at. With that in mind, we are able to binarily narrow our focus down until we find the right value.

For fun, I decided to write some helper methods to compare the efficiencies of the two algorithms. First here's an unpleasant, yet working, piece of code to generate a large array with a single magic index randomly located inside of it. Try not to get too lost inside of the abyss.

  def big_arr_with_magic_index
    arr = []
    cur = rand(1_000_000) * -1
    while arr.length < 1_000_000
      arr << cur unless cur == arr.length
      cur += (rand(10) + 1)
    end
    i = 1
    loop do
      break if arr[i + 1].nil?
      if i > arr[i - 1] && i < arr[i + 1]
        arr[i] = i
        break
      end
      i += 1
    end
    arr = big_arr_with_magic_index unless contains_magic_index?(arr) &&
    arr.min < -500_000
    arr
  end

  def contains_magic_index?(arr)
    arr.each_with_index { |v,i| return true if v == i}
    false
  end

This code just creates a sequential array of sorta-randomly dispersed elements, checks to see if the array contains a magic index and returns it if it does.

And here are the benchmarking methods for completeness

  def benchmark(method, arr)
    start = Time.now
    send(method.to_sym, arr)
    Time.now - start
  end

  def benchmarks
    5.times do |i|
      puts "Round #{i}"
      big_arr = big_arr_with_magic_index
      regular =  benchmark(:find_magic_index, big_arr)
      binary =  benchmark(:binary_find_magic_index, big_arr)

      puts "Linear method took #{regular} "
      puts "Binary method took #{binary} "
      puts "Binary was about #{regular/binary} times faster"
    end
  end

And finally the results.

  Round 0
  Linear method took 0.01340232
  Binary method took 0.001095561
  Binary was about 12.23329417531292 times faster
  Round 1
  Linear method took 0.025097481
  Binary method took 0.001062092
  Binary was about 23.63023259755276 times faster
  Round 2
  Linear method took 0.024860914
  Binary method took 0.001058729
  Binary was about 23.481848518364945 times faster
  Round 3
  Linear method took 0.023043551
  Binary method took 0.001084791
  Binary was about 21.242387704175272 times faster
  Round 4
  Linear method took 0.015505895
  Binary method took 0.001071029
  Binary was about 14.477567834297671 times faster

It would appear that binary search performs (roughly) 18 times faster than the linear route. In a world where page load times are counted in milliseconds, that's an important measurement to remember!

Thanks for reading and I hope you enjoyed!