JavaScript Coding Test Course, Binary Search

Binary Search is an efficient algorithm for finding a specific value in a sorted array. The basic idea of binary search is to repeatedly narrow down the portion of the array that contains the desired value by splitting the array in half. In this article, we will provide a detailed explanation of the binary search algorithm and solve a problem using it.

Problem Description

The following is a problem that can be solved using binary search:

Problem: Find a specific value in an array using binary search

Given a sorted array nums and an integer target, return the index of target. If target does not exist in the array, return -1. The function assumes that nums is sorted in ascending order.

Examples

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

Principle of the Binary Search Algorithm

The binary search algorithm proceeds with the following steps:

  1. Calculate the middle index of the array.
  2. Compare the middle value with the desired value (target):
    • If the middle value is equal to the target, return the middle index.
    • If the middle value is less than the target, search the right half. (from middle index + 1 to the end)
    • If the middle value is greater than the target, search the left half. (from the start to middle index – 1)
  3. Repeat this process until the exact value is found.

The time complexity of binary search is O(log n), which allows for quick searches in large datasets.

Problem-Solving Process

Now, let’s write the code to solve the above problem. First, we define a function that accepts the array and target.


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

    while (left <= right) {
        const mid = Math.floor((left + right) / 2); // calculate the middle index
        
        if (nums[mid] === target) {
            return mid; // return middle index if found
        } else if (nums[mid] < target) {
            left = mid + 1; // move to the right half
        } else {
            right = mid - 1; // move to the left half
        }
    }

    return -1; // return -1 if the value does not exist
}

Code Explanation

In the above code, the binarySearch function performs binary search on the nums array using the target value as an argument.

  1. Sets the search range using the left and right variables. The initial values are the start and end indices of the array, respectively.
  2. Uses a while loop to repeat while left is less than or equal to right.
  3. Calculates the middle index each iteration and compares the middle value with the target.
  4. Adjusts the search range based on conditions and ultimately returns -1 if the value is not found.

Example Execution

Below is an example execution of the binary search function:


const nums = [-1,0,3,5,9,12];
console.log(binarySearch(nums, 9)); // Output: 4
console.log(binarySearch(nums, 2)); // Output: -1

Result Analysis

Through the above examples, we can see that the function outputs the correct index. binarySearch(nums, 9) returns 4, and binarySearch(nums, 2) returns -1.

Conclusion

Binary search is a very efficient search algorithm that allows for a quick search of desired values in sorted data. I hope this lecture has helped you understand the principles and implementation methods of binary search. Since it is also a common algorithm that appears in coding tests, it is essential to familiarize yourself with it and practice.