Binary Search Algorithm

Binary search is a searching algorithm that finds the position of a target value within a sorted array or list. It is a divide-and-conquer algorithm that works by repeatedly dividing the search interval in half.

Binary search is efficient for searching in large datasets because it reduces the search space by half with each comparison. Its time complexity is O(log n), where n is the number of elements in the array.

Binary Search Algorithm Implementation in JavaScript:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    // Find the middle index
    let mid = Math.floor((left + right) / 2);

    // Check if the middle element is the target
    if (arr[mid] === target) {
      return mid; // Target found, return its index
    } else if (arr[mid] < target) {
      // If target is greater, ignore the left half
      left = mid + 1;
    } else {
      // If target is smaller, ignore the right half
      right = mid - 1;
    }
  }

  return -1; // Target not found
}

// Example usage:
const sortedArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const targetValue = 7;

const result = binarySearch(sortedArray, targetValue);

if (result !== -1) {
  console.log(`Element ${targetValue} found at index ${result}.`);
} else {
  console.log(`Element ${targetValue} not found in the array.`);
}
binary search algorithm
Image from wikipedia https://en.wikipedia.org/wiki/Binary_search_algorithm

The code above implements the binary search algorithm to find a target element within a sorted array. It starts by initializing two pointers, left and right, which represent the range of the array to search. While the left pointer is less than or equal to the right pointer, it calculates the middle index of the array. It then checks if the element at the middle index is equal to the target. If it is, it returns the index of the target. If the middle element is less than the target, it updates the left pointer to search the right half of the array. Conversely, if the middle element is greater than the target, it updates the right pointer to search the left half of the array. This process continues until the target is found or the pointers cross each other, indicating that the target is not present in the array. If the target is not found, the function returns -1.

We can make few changes in our previous approach to implement binary search algorithm but it’s the same concept as we discussed already.

function binary_search_alternative(A, n, T) {
    let L = 0;
    let R = n - 1;

    while (L !== R) {
        const m = Math.ceil((L + R) / 2);
        if (A[m] > T) {
            R = m - 1;
        } else {
            L = m;
        }
    }

    if (A[L] === T) {
        return L;
    }

    return "unsuccessful";
}

// Example usage:
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17];
const target = 11;
console.log(binary_search_alternative(arr, arr.length, target)); // Output: 5 (index of the target element)

Binary Search Algorithm Implementation in Python:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        mid_value = arr[mid]

        if mid_value == target:
            return mid  # Target found, return its index
        elif mid_value < target:
            low = mid + 1  # Target is in the right half
        else:
            high = mid - 1  # Target is in the left half

    return -1  # Target not found

# Example usage:
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target_value = 7
result = binary_search(sorted_array, target_value)

if result != -1:
    print(f'Target {target_value} found at index {result}.')
else:
    print(f'Target {target_value} not found in the array.')

Before applying the binary search algorithm, ensure that the array is sorted in ascending order. If the array is not sorted, you’ll need to sort it first, which typically has a time complexity of O(n log n) using efficient sorting algorithms like merge sort or quicksort.

To sort an array in JavaScript you can use sort() array method .

const arr = [5, 2, 8, 1, 4];
arr.sort(); // Sorts the array in ascending order
console.log(arr); // Output: [1, 2, 4, 5, 8]

Don't Miss Out! Subscribe to Read Our Latest Blogs.

If you found this blog helpful, share it on social media.

Subscription form (#5)

Leave a Comment

Your email address will not be published. Required fields are marked *

Pin It on Pinterest

Scroll to Top