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.

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!