Welcome to today's lesson! We're diving into Binary Search, a clever technique for locating specific elements within a sorted list. By repeatedly dividing the search interval in half, we can efficiently find the targeted item. Think of it as flipping through a dictionary — rather than going page by page, you'd start in the middle, then narrow down the section in half until you find your desired word.
Binary Search begins at the midpoint of a sorted list, halving the search area at each step until it locates the target. For example, if you are looking for the number 8 in a sorted list ranging from 1 to 10, you would start at 5. Since 8 is larger than the midpoint, you narrow the search to the second half of the list, leaving you with numbers 6 to 10. In this new sublist, the middle number is 8, and thus, you've found your target. This efficient approach significantly reduces the number of comparisons needed compared to a linear search.
Let's see how Binary Search can be implemented in Ruby, taking a recursive approach. This process involves a function calling itself — with a base case in place to prevent infinite loops — and a recursive case to solve smaller parts of the problem.
Ruby1def binary_search(arr, start, end_index, target) 2 return -1 if start > end_index # Base case 3 4 mid = start + (end_index - start) / 2 # Find the midpoint 5 6 return mid if arr[mid] == target # Target found 7 8 if arr[mid] > target # If the target is less than the midpoint 9 binary_search(arr, start, mid - 1, target) # Search the left half 10 else 11 binary_search(arr, mid + 1, end_index, target) # Search the right half 12 end 13end
In this Ruby code, the base case is defined first. If the start index is greater than the end_index, it indicates the search area is exhausted, resulting in a -1 return. The code then locates the midpoint. If the midpoint equals our target, it’s returned. Depending on whether the target is less or more than the midpoint, the search continues within the left or right half, respectively.
Let's analyze the time complexity of Binary Search, which measures how much time an algorithm takes as the input size increases. Notably, Binary Search halves the list at every step, necessitating log(n) steps for an array of size n. Therefore, the time complexity of Binary Search is O(log n).
You can also implement the Binary Search algorithm iteratively using a while loop. Here is the Ruby code for the iterative approach.
Ruby1def binary_search_iterative(arr, target) 2 start = 0 3 end_index = arr.length - 1 4 5 while start <= end_index 6 mid = start + (end_index - start) / 2 7 return mid if arr[mid] == target 8 9 if arr[mid] < target 10 start = mid + 1 11 else 12 end_index = mid - 1 13 end 14 end 15 -1 16end
Instead of dividing the array recursively, this code uses a while loop, which continues until the start index is equal to or less than the end_index. The middle element is found the same way as in the recursive approach. If the target is equal to this middle element, we have found our target. On the other hand, if the target is greater than the middle element, we adjust the start index to be one position after the middle index. However, if the target is less than the middle element, we adjust the end_index to be one position before the middle index.
Both the recursive and iterative versions of the Binary Search algorithm have a time complexity of O(log(n)), making them both very efficient.
In Ruby, the iterative version generally uses less memory compared to recursion due to the absence of multiple stack frames, which are required when using recursion. Ruby has default settings that can limit the depth of recursion you can achieve without hitting stack overflow errors. While recursion often leads to cleaner and more readable code, understanding and deciding between recursion or iteration involves balancing concerns of readability with potential memory limitations.
Binary Search is a smart method for locating specific items within a sorted list. By repeatedly narrowing down the search area, it finds the target until the search area is reduced to zero. The key to mastering these concepts lies in practice. Starting with straightforward tasks, we will gradually navigate toward more complex problems that showcase the strength of Binary Search. Great job!
