binary-search

Understanding Binary Search

Binary search is a powerful algorithm used to efficiently find the position of a target value within a sorted array or list. Its effectiveness lies in its ability to eliminate half of the remaining elements in each step, resulting in a logarithmic time complexity of O(log n), where n is the number of elements in the array.

Let’s break down how binary search works and provide a practical example in JavaScript.

How Binary Search Works

1 – Initial Setup:

  • Start with a sorted array.
  • Set two pointers, low and high, to the first and last indices of the array.

2 – Middle Element:

  • Find the middle element of the array: mid = Math.floor((low + high) / 2).

3 – Comparison:

  • Compare the middle element with the target value.

4 – Three Possible Cases:

  • If the middle element is equal to the target value, the search is successful.
  • If the middle element is greater than the target, update high to mid - 1 and search in the left half.
  • If the middle element is less than the target, update low to mid + 1 and search in the right half.

5 – Repeat:

    • Repeat steps 2-4 until the target value is found or low exceeds high.

    6 – Termination:

    • If low is greater than high, the target value is not in the array.

    Example in JavaScript

    Let’s implement a binary search algorithm in JavaScript:

    function binarySearch(arr, target) {
      let low = 0;
      let high = arr.length - 1;
    
      while (low <= high) {
        const mid = Math.floor((low + high) / 2);
    
        if (arr[mid] === target) {
          return mid; // Target found, return the index
        } else if (arr[mid] > target) {
          high = mid - 1; // Search in the left half
        } else {
          low = mid + 1; // Search in the right half
        }
      }
    
      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(`Target ${targetValue} found at index ${result}.`);
    } else {
      console.log(`Target ${targetValue} not found in the array.`);
    }

    In this example, we use a binarySearch function to find the index of a target value in a sorted array. The function returns the index if the target is found and -1 otherwise.

    Feel free to use this binary search algorithm in your projects when dealing with sorted data. Its efficiency makes it a valuable tool, especially for large datasets. Happy coding!


    Leave a Reply

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


    Categories


    Tag Cloud

    .net algorithms angular api Array arrays async asynchronous basic-concepts big o blazor c# classes code components containers control-structures csharp data structures data types dictionaries docker dom dotnet framework functions git guide Inheritance javascript json leetcode linq lists loops methods MVC npm object oriented programming oop operators sorted try catch typescript web framework