Binary Search Algorithm (With Code in C++ / Python / Java)

Binary search is an efficient algorithm for finding the position of a target value within a sorted array. It works by repeatedly dividing the search interval in half until the value is found or it is clear that the value is not present in the array.

ALGORITHM :

Here is an overview of the binary search algorithm:

1. Set the lower and upper bounds of the search interval to the first and last elements of the array, respectively.
2. If the search interval is empty (the lower bound is greater than the upper bound), the target value is not present in the array and the search is terminated.
3. Calculate the midpoint of the search interval.
4. If the target value is equal to the value at the midpoint, the search is successful and the position of the target value is returned.
5. If the target value is less than the value at the midpoint, set the upper bound of the search interval to the midpoint – 1 and go back to step 2.
6. If the target value is greater than the value at the midpoint, set the lower bound of the search interval to the midpoint + 1 and go back to step 2.

There are two main approaches to implementing binary search:

• Iterative Method:
• Recursive Method:

Iterative Method:

The iterative method involves using a loop to perform the search.

Here is an example of the binary search algorithm implemented using a recursive method in C++:

int binarySearch(int arr[], int target, int low, int high) {
  while (low <= high) {
    int mid = (low + high) / 2;  // Calculate midpoint
    if (arr[mid] == target) {
      return mid;  // Target found at midpoint
    } else if (arr[mid] < target) {
      low = mid + 1;  // Search right half
    } else {
      high = mid - 1;  // Search left half
    }
  }
  return -1;  // Target not found
}

Recursive Method:

The recursive method involves using a function to perform the search.

Here is an example of the binary search algorithm implemented using a recursive method in C++:

int binarySearch(int arr[], int target, int low, int high) {
  if (low > high) {
    return -1;  // Target not found
  }
  int mid = (low + high) / 2;  // Calculate midpoint
  if (arr[mid] == target) {
    return mid;  // Target found at midpoint
  } else if (arr[mid] < target) {
    return binarySearch(arr, target, mid + 1, high);  // Search right half
  } else {
    return binarySearch(arr, target, low, mid - 1);  // Search left half
  }
}

Here is the same algorithm implemented in Python:

def binary_search(arr, target, low, high):
  if low > high:
    return -1  # Target not found
  mid = (low + high) // 2  # Calculate midpoint
  if arr[mid] == target:
    return mid  # Target found at midpoint
  elif arr[mid] < target:
    return binary_search(arr, target, mid + 1, high)  # Search right half
  else:
    return binary

Here is the binary search algorithm implemented using an iterative method in Java:

public int binarySearch(int[] arr, int target, int low, int high) {
  while (low <= high) {
    int mid = (low + high) / 2;  // Calculate midpoint
    if (arr[mid] == target) {
      return mid;  // Target found at midpoint
    } else if (arr[mid] < target) {
      low = mid + 1;  // Search right half
    } else {
      high = mid - 1;  // Search left half
    }
  }
  return -1;  // Target not found
}