Binary Search: The Power of Dividing and Conquering

Binary search is a popular algorithm used for searching a sorted array or list. It works by repeatedly dividing the search space in half until the desired element is found or the search space is exhausted.

Binary search is a very efficient algorithm for finding a specific value in a sorted collection of values. It can be used in a wide range of applications, such as:

Searching for an element in a sorted array: Binary search can be used to quickly find the position of an element in a sorted array, which can be useful in many data processing tasks.

Finding a value within a range: Binary search can be used to find the smallest or largest element in a sorted array that satisfies a given condition. For example, it can be used to find the first or last occurrence of a value in an array.

Implementing data structures: Binary search can be used to implement various data structures, such as binary trees and heaps, which are used in computer science for efficient storage and retrieval of data.

Optimization problems: Binary search can be used to optimize the value of a function by finding the value of an input parameter that maximizes or minimizes the function output.

Overall, binary search is a powerful algorithm that is widely used in computer science and many other fields that require efficient search and retrieval of data.

Binary Search in Ruby

Here’s how you can implement binary search in Ruby:

def binary_search(arr, target)
  left = 0
  right = arr.length - 1
  
  while left <= right do
    mid = (left + right) / 2
    if arr[mid] == target
      return mid
    elsif arr[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end
  
  return -1 # element not found
end

The binary_search function takes two arguments: the arr array to search and the target element to find. It initializes two pointers: left and right that point to the first and last indices of the array, respectively.

The function then enters a while loop that continues as long as the left pointer is less than or equal to the right pointer. At each iteration of the loop, the function calculates the mid index by taking the average of the left and right pointers.

If the arr[mid] element is equal to the target, the function returns the mid index as the position of the target in the array. If arr[mid] is less than the target, the function updates the left pointer to mid + 1 to search the right half of the array. Otherwise, the function updates the right pointer to mid - 1 to search the left half of the array.

If the target element is not found in the array, the function returns -1.

Here’s an example of how to use the binary_search function:

arr = [1, 3, 5, 7, 9]
target = 5

puts binary_search(arr, target) # Output: 2

In this example, the arr array contains the elements 1, 3, 5, 7, 9. The binary_search function is called with the arr array and the target element of 5. The function returns the index 2, which is the position of the 5 element in the array.

Binary Search in Javascript

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1; // element not found
}

The implementation is very similar to the Ruby implementation, but uses let and const keywords to declare variables, and arrow functions are not used in this case.

In the binarySearch function, the input array arr and target element target are taken as parameters. The function initializes two pointers left and right that point to the first and last indices of the array, respectively.

The function then enters a while loop that continues as long as the left pointer is less than or equal to the right pointer. At each iteration of the loop, the function calculates the mid index by taking the average of the left and right pointers using Math.floor method.

If the arr[mid] element is equal to the target, the function returns the mid index as the position of the target in the array. If arr[mid] is less than the target, the function updates the left pointer to mid + 1 to search the right half of the array. Otherwise, the function updates the right pointer to mid - 1 to search the left half of the array.

If the target element is not found in the array, the function returns -1.

Here’s an example of how to use the binarySearch function:

const arr = [1, 3, 5, 7, 9];
const target = 5;

console.log(binarySearch(arr, target)); // Output: 2

In this example, the arr array contains the elements 1, 3, 5, 7, 9. The binarySearch function is called with the arr array and the target element of 5. The function returns the index 2, which is the position of the 5 element in the array.

What is the space time complexity of binary search?

The time complexity of binary search algorithm is O(log n) where n is the size of the input array. This is because at each iteration of the while loop, the search space is divided in half, so the number of iterations required to find the target element is proportional to the logarithm of the input size.

The space complexity of binary search algorithm is O(1) because it only requires a constant amount of memory to store the pointers and variables used in the algorithm, regardless of the size of the input array.

Therefore, the space-time complexity of the binary search algorithm can be expressed as O(log n) for time complexity and O(1) for space complexity.