Lesson 2

Binary Search in JavaScript: Unraveling the Algorithm and Complexity

Lesson Introduction and Overview

Greetings! Today, we're exploring Binary Search, an efficient algorithm that pinpoints elements in a sorted list. It's like finding a house number on a long street — instead of starting from one end, you begin in the middle and, based on whether the house number is higher or lower, you search the right or left half of the list.

We'll learn to:

  1. Understand Binary Search.
  2. Implement Binary Search using recursion and iteration in JavaScript.
  3. Analyze the time complexity of Binary Search.
Unveiling Binary Search

Binary Search follows a divide-and-conquer strategy. It starts in the middle of a sorted list. If the middle value is the desired one, great! If not, it uses the sorted nature of the list to eliminate half of it. The side to eliminate is selected based on whether the target is smaller or larger than the middle value.

Implementing Binary Search Using Recursion in JavaScript

Let's implement Binary Search in JavaScript using recursion. Here's the code, accompanied by detailed comments:

JavaScript
1function recursiveBinarySearch(arr, start, end, target) { 2 // Base case: the search area is empty 3 if (start > end) return -1; 4 5 // Find the midpoint 6 let mid = Math.floor((start + end) / 2); 7 8 // Found the target 9 if (arr[mid] == target) return mid; 10 11 // If the target is less than the midpoint, search the left half 12 if (arr[mid] > target) 13 return recursiveBinarySearch(arr, start, mid - 1, target); 14 15 // Else, search the right half 16 return recursiveBinarySearch(arr, mid + 1, end, target); 17}

This function calls itself recursively, gradually shrinking the search area until it finds the target.

Implementing Binary Search Using Iteration in JavaScript

Here, we create a Binary Search using a while loop in JavaScript:

JavaScript
1function iterativeBinarySearch(arr, target) { 2 let start = 0; 3 let end = arr.length - 1; 4 5 while (start <= end) { 6 let mid = Math.floor((start + end) / 2); 7 if (arr[mid] == target) return mid; // Found the target 8 if (arr[mid] < target) start = mid + 1; // Search the right half 9 else end = mid - 1; // Search the left half 10 } 11 return -1; 12}

In this version, the function does not call itself. Instead, it uses a while loop to achieve the same goal.

Analyzing Complexity of Binary Search

Binary Search reduces the input size by half on every step, hence it takes log(n) steps to find a target in an array of size n. Thus, the time complexity of Binary Search is O(log n).

Both recursive and iterative approaches share the same time complexity — O(log n). Their choice usually comes down to specific problems, constraints, and personal preferences.

Lesson Summary and Preview of Practice Exercises

Great job! You've grasped the core of Binary Search, implemented it in JavaScript, and explored its time complexity. Up next, we have practice exercises to help you master Binary Search. Happy coding, and see you in the practice session!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.