Data Structures and Algorithms in JavaScript: Binary Search, Merge Sort, Quick Sort

1. Binary Search

Complexity O(log n).

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; // Target found, return index
    } else if (arr[mid] < target) {
      left = mid + 1; // Target is in the right half
    } else {
      right = mid - 1; // Target is in the left half
    }
  }

  return -1 // Target not found
}

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

const result = binarySearch(sortedArray, targetElement)

if (result !== -1) {
  console.log(`${targetElement} found at index ${result}`)
} else {
  console.log(`${targetElement} not found in the array`)
}

2. Merge Sort

Complexity (all cases): O(n log n).

Divide Phase: O(log n), Conquer (Merge) Phase: O(n). Combining the Phases: Since there are O(log n) levels (from the divide phase) and each level requires O(n) time (from the conquer phase), the overall time complexity of Merge Sort is O(n log n).

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr
    }

    // Finding the middle of the array
    const middle = Math.floor(arr.length / 2)

    // Dividing the array into two halves
    const left = arr.slice(0, middle)
    const right = arr.slice(middle)

    // Using recursion to combine the two halves
    return merge(
        mergeSort(left), mergeSort(right)
    )
}

// Merge the two halves in a sorted manner
function merge(left, right) {
    let resultArray = [], leftIndex = 0, rightIndex = 0

    // Concatenating values into the resultArray in order
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex])
            leftIndex++ // move left array cursor
        } else {
            resultArray.push(right[rightIndex])
            rightIndex++ // move right array cursor
        }
    }

    // We need to concatenate here because there will be one element remaining
    // from either left OR the right
    return resultArray
            .concat(left.slice(leftIndex))
            .concat(right.slice(rightIndex))
}

// Example usage:
const array = [12, 11, 13, 5, 6, 7]
console.log("Original Array:", array)

const sortedArray = mergeSort(array)
console.log("Sorted Array:", sortedArray)

3. Quick Sort

Complexity: O(n log n) or O(n²).

Best and Average Case: O(n log n).

Worst Case: O(n²).

Each partition operation, which involves going through each element, takes linear time (O(n)), and the logarithmic number of partitioning levels (log n) leads to the O(n log n) complexity. The worst-case scenario for QuickSort occurs when the partitioning routine consistently produces one very small and one very large partition. This can happen if the pivot element chosen is always the smallest or largest in the list. In such cases, the depth of recursion becomes linear (O(n)), and since each level of recursion involves a linear scan of the array, the overall time complexity becomes quadratic, O(n²).

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }

  const pivot = arr[0]
  const left = []
  const right = []

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  return [...quickSort(left), pivot, ...quickSort(right)]
}

// Example usage:
const unsortedArray = [5, 3, 7, 2, 8, 4, 1, 6]
const sortedArray = quickSort(unsortedArray)
console.log(sortedArray)