More Code Puzzles for Ruby... Interview Cake examples part 2

More Code Puzzles for Ruby...

(from Interview cake)

Given a sorted array of integers , write a method to check if a number is in the array. Focus on doing this quickly.

    This is essentially asking us to implement a binary search. You could approach this with more of a brute force approach, by iterating through the entire array and checking each value to see if it matches the value you are looking for, however with binary search we cut the array in half and then half again and then half again... (recursion!). We define a function that takes in our array, and the number we are searching for. The function also starts with two default arguments 'from' and 'to'. We assign the value of 'from' as 0 initially, because this is telling us where in the array to start. 'to' is initially set to nil, because we will dynamically assign this to represent the last index of the array. The first thing we do in the array is check the value of 'to', if it is nil then we reassign it to be the last index of our array. Next we assign a 'mid' variable. This 'mid' variable is intended to represent the index of the value that is in the middle of the array. Next we check to see if our value is greater than the value at our 'mid' index. If it is we recursively call our function, this time passing in our array, our number , and then 'mid+1', and our 'to' value. What this does is, runs through our code again, but this time it has a new starting position to begin our check. We've essentially cut our array in half. Since we know that the the array is sorted and the number we are looking for is greater than the mid point, there is no need to look at anything from array[0] to array[mid]. The same logic is at play if our value is less than the 'mid' value. Each time the method is recursively called, we divide our array in half, until the number we are looking for is equal to our value of our 'mid' index. That index is then returned.