704. Binary Search

EasyArrayBinary Search
Leetcode Link

Problem Description

This problem asks us to create a function that takes two inputs: an array of integers nums sorted in ascending order, and an integer target. The goal is to search for the target value within the nums array. If the target is found, the function should return the index of the target in the array. If target is not in the array, the function should return -1.

The critical constraint is that the algorithm used to search for the target value must have a runtime complexity of O(log n). This is a strong hint that a binary search algorithm should be implemented because binary search has a logarithmic time complexity and typically operates on sorted data.

Intuition

To satisfy the O(log n) runtime complexity requirement, we use a binary search algorithm, which effectively splits the array in half during each iteration to narrow down the possible location of the target value.

Here are the key steps of the intuition behind the binary search solution approach:

  1. Initialize two pointers, left and right, which represent the start and end of the range within the array we're currently considering. Initially, left is 0 and right is len(nums) - 1.
  2. Enter a while loop which runs as long as left is less than right. This loop will continue until we either find the target or the search space is empty.
  3. Determine the mid point index by averaging left and right. The >> 1 operation is a bitwise shift that divides the sum by 2, efficiently finding the midpoint.
  4. Compare the middle element nums[mid] with the target. If nums[mid] is greater than or equal to the target, we move the right pointer to mid, as the target, if it exists, must be to the left of mid.
  5. If nums[mid] is less than the target, the target, if it exists, must be to the right of mid, so we update left to mid + 1.
  6. The loop continues, halving the search space each time, until left becomes equal to right.
  7. After exiting the loop, we check if nums[left] is equal to target. If it is, we return left, which is the index of the target. If not, we return -1 to indicate that the target is not present in the array.

This solution approaches the problem using classic binary search, ensuring the runtime complexity meets the required O(log n) by continuously halving the search space, which is characteristic of logarithmic runtime algorithms.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The implementation of the solution uses a binary search algorithm. Binary search is a classic algorithm in computer science for efficiently searching for an element in a sorted list. The algorithm repeatedly divides the search interval in half, and because the list is sorted, it can quickly determine if the element can only be in either the left or the right half of the list.

Here's a step-by-step walkthrough of the implementation based on the provided code:

  1. Initialize two pointers: left is set to 0, which is the first index of nums, and right is set to len(nums) - 1, which is the last index of nums.

  2. Enter a while loop that continues as long as left is less than right. This ensures that we don't stop searching until the search space has been fully narrowed down. We're searching for the exact placement of the target or concluding that it's not in the array.

  3. Calculate the mid-point index mid by adding left and right, then shifting the result to the right by one bit (>> 1). This is equivalent to mid = (left + right) // 2 but is more efficient. The mid variable represents the index of the element in the middle of the current search space.

  4. The if statement if nums[mid] >= target: evaluates whether the middle element is greater than or equal to the target. If so, that means the target, if it exists, must be at mid or to the left of mid within the search space. In response, right is updated to mid, narrowing the search to the left half of the current search space (inclusive of the mid point).

  5. If the middle element is less than the target, the target can only be to the right of mid. Therefore, we update left to be mid + 1, now searching to the right of the original mid point.

  6. The loop continues until left is equal to right, which means we can no longer divide the search space, and we must check if we have found the target.

  7. Once the loop exits, we have one final check to perform. We compare the element at the index left with the target. If they're equal, then left is the index where target is found in the array nums. Otherwise, if they're not equal, this means the target is not present in the array, and we return -1.

No other data structures are utilized in this implementation as binary search operates directly on the sorted input list, and no additional memory is required other than a few variables for indices.

This solution leverages the efficiency of binary search, taking advantage of the sorted nature of the input array nums to deliver the expected outcome within the required O(log n) time complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Example Walkthrough

Let's consider an example to illustrate the solution approach described above.

Suppose we have the following array of integers nums and a target integer target:

1nums = [1, 3, 5, 6, 9]
2target = 5

Here's how the binary search algorithm would be applied step by step:

  1. Initialize two pointers: left = 0 (beginning of the array) and right = 4 (index of the last element in the array).

  2. Our while loop starts because left (0) is less than right (4).

  3. Calculate mid index: mid = (0 + 4) >> 1 = 4 >> 1 = 2 (bitwise shift of 4 to the right by 1 is the same as integer division by 2). The element at index 2 in nums is 5.

  4. Check if nums[mid] >= target. In this case, nums[2] is 5, which is equal to target (5). Therefore, we found our target, and right is updated to mid.

  5. The array is not further divided since we already located the target. Therefore, the while loop does not continue further.

  6. The loop concludes, and we no longer need to narrow down our search.

  7. Finally, outside of the loop, we compare nums[left] with target. Here, nums[left] is nums[2] which is 5, and this is equal to the target value. We return left, which is 2, the index where target is found.

By following this method, we efficiently find our target using a binary search approach, ensuring the search process conforms to the logarithmic runtime, O(log n).

Solution Implementation

1from typing import List
2
3class Solution:
4    def search(self, nums: List[int], target: int) -> int:
5        # Initialize the left and right pointers
6        left, right = 0, len(nums) - 1
7      
8        # Use a binary search algorithm
9        while left < right:
10            # Calculate the middle index using bit shifting (equivalent to floor division by 2)
11            mid = (left + right) >> 1
12          
13            # If the middle element is greater than or equal to the target
14            if nums[mid] >= target:
15                # Narrow the search to the left half including the middle element
16                right = mid
17            else:
18                # Narrow the search to the right half excluding the middle element
19                left = mid + 1
20      
21        # After exiting the loop, left should be the smallest index of the target value
22        # Check if the element at the left index is the target
23        return left if nums[left] == target else -1
24        # If the element is not found, return -1
25
26# Example usage
27# sol = Solution()
28# result = sol.search([1, 2, 3, 4, 5], 3)
29# print(result) # Output: 2
30
1class Solution {
2    public int search(int[] nums, int target) {
3        // Initialize the starting index of the search range.
4        int left = 0;
5        // Initialize the ending index of the search range.
6        int right = nums.length - 1;
7
8        // Continue searching while the range has more than one element.
9        while (left < right) {
10            // Calculate the middle index of the current range.
11            int mid = left + (right - left) / 2;
12
13            // If the middle element is greater than or equal to the target,
14            // narrow the search range to the left half (including the middle element).
15            if (nums[mid] >= target) {
16                right = mid;
17            } else {
18                // If the middle element is less than the target,
19                // narrow the search range to the right half (excluding the middle element).
20                left = mid + 1;
21            }
22        }
23
24        // At this point, left is the index where the target may be if it exists.
25        // Check if the element at the 'left' index is the target.
26        // If it is, return the index. Otherwise, return -1 indicating the target is not found.
27        return nums[left] == target ? left : -1;
28    }
29}
30
1#include <vector> // Include the vector header for using the std::vector container
2
3class Solution {
4public:
5    int search(std::vector<int>& nums, int target) {
6        int left = 0; // Initialize left boundary of the search
7        int right = nums.size() - 1; // Initialize right boundary of the search
8      
9        // Perform binary search
10        while (left < right) {
11            // Calculate the midpoint to avoid potential overflow
12            int mid = left + (right - left) / 2;
13          
14            // If the middle element is greater or equal to the target,
15            // we need to move the right boundary to the middle
16            if (nums[mid] >= target) {
17                right = mid;
18            } else {
19                // The target is greater than the middle element,
20                // move left boundary one step to the right of mid
21                left = mid + 1;
22            }
23        }
24      
25        // After the loop ends, left should point to the smallest
26        // number not smaller than target. Check if it's the target,
27        // otherwise return -1 as the target is not found
28        return (nums[left] == target) ? left : -1;
29    }
30};
31
1/**
2 * Searches for a target value in a sorted array of numbers using binary search.
3 * 
4 * @param {number[]} nums - Sorted array of numbers where we search for the target.
5 * @param {number} target - The value to search for.
6 * @return {number} The index of the target if found; otherwise, -1.
7 */
8const search = (nums: number[], target: number): number => {
9    // Initialize left and right pointers for the binary search.
10    let left: number = 0;
11    let right: number = nums.length - 1;
12
13    // Continue to search while the left pointer has not surpassed the right.
14    while (left < right) {
15        // Calculate the middle index using bitwise right shift
16        // equivalent to Math.floor((left + right) / 2)
17        const mid: number = (left + right) >> 1;
18
19        // If the middle element is greater or equal to target, move the right pointer to the middle.
20        if (nums[mid] >= target) {
21            right = mid;
22        } else {
23            // If the middle element is less than the target, move the left pointer past the middle.
24            left = mid + 1;
25        }
26    }
27
28    // Once the search space is narrowed down to a single element,
29    // check if it's equal to the target and return the appropriate index or -1.
30    return nums[left] === target ? left : -1;
31};
32
33// Example usage:
34const nums: number[] = [1, 3, 5, 7, 9];
35const target: number = 7;
36const result: number = search(nums, target); // result should be 3 as nums[3] = 7
37
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

Time Complexity:

The given Python code performs a binary search on the array nums by repeatedly dividing the search interval in half. The search ends when left and right indices converge, at which point it either finds the target or concludes that the target is not in the array.

The while loop will run until left is equal to right. On each iteration, the interval size is halved, which means the time complexity is logarithmic with regard to the size of the array nums. Hence, the time complexity is O(log n), where n is the length of nums.

Space Complexity:

The space complexity of the code is O(1) since it uses a constant amount of extra space. The variables left, right, and mid only take up a fixed amount of space regardless of the input list size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the relationship between a tree and a graph?

Recommended Readings

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫