Jobs

Interviews

Discussions

Binary Search

Easy

Asked by:

More companies

40 views

Topics:

ArraysBinary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 10⁴
-10⁴ < nums[i], target < 10⁴
All the integers in nums are unique.
nums is sorted in ascending order.

Try coding it in LeetCode

Binary Search

Easy

Asked by:

40 views

Topics:

ArraysBinary Search

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Constraints:

1 <= nums.length <= 10⁴
-10⁴ < nums[i], target < 10⁴
All the integers in nums are unique.
nums is sorted in ascending order.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input array guaranteed to be sorted in ascending order?
Can the target value appear multiple times in the array, and if so, which index should I return (e.g., the first occurrence)?
What should I return if the target value is not found in the array?
Can the input array be empty?
What is the range of possible values in the array and for the target?

Brute Force Solution

Approach

The brute force approach to searching a sorted list is like manually checking every item until you find the one you're looking for. It's straightforward: you simply go through each item in order, one by one, until you locate the target value.

Here's how the algorithm would work step-by-step:

Start by looking at the very first item in the list.
Check if that item is the thing you're searching for.
If it's not, move to the next item in the list.
Repeat this process of checking each item until you either find the item you're looking for or you reach the end of the list.
If you reach the end of the list without finding the item, it means the item is not in the list.

Code Implementation

def linear_search(sorted_list, target_value):
    list_length = len(sorted_list)

    # Iterate through each element in the sorted list.
    for current_index in range(list_length):
        current_element = sorted_list[current_index]

        # Check if the current element matches the target.
        if current_element == target_value:
            return current_index

        # Exit early if we surpass the target, due to list being sorted
        if current_element > target_value:
            return -1

    # Return -1 if target isn't found after checking all elements.
    return -1

Big(O) Analysis

Time Complexity

O(n) – The provided approach iterates through the list sequentially, checking each element until the target is found or the end of the list is reached. In the worst-case scenario, the target is the last element or not present, requiring us to examine all 'n' elements of the list. Therefore, the time complexity is directly proportional to the input size 'n', resulting in O(n) time complexity.

Space Complexity

O(1) – The brute force approach iterates through the list using a single index. No additional data structures are used to store intermediate results or visited items. The memory required for the index variable remains constant irrespective of the size N of the input list. Therefore, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to find a specific value in a sorted list is to repeatedly cut the list in half. We eliminate half of the remaining possibilities with each step, quickly narrowing down our search.

Here's how the algorithm would work step-by-step:

Start by looking at the middle value of the list.
If the middle value is what you're looking for, you're done!
If the value you're looking for is less than the middle value, you know it must be in the first half of the list. So, discard the second half and repeat the process on the first half.
If the value you're looking for is greater than the middle value, you know it must be in the second half of the list. Discard the first half and repeat the process on the second half.
Keep repeating this 'divide and conquer' approach until you find the value or the list becomes empty. If the list becomes empty, the value is not in the list.

Code Implementation

def binary_search(sorted_list, target_value):
    left_index = 0
    right_index = len(sorted_list) - 1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2
        middle_value = sorted_list[middle_index]

        # Found the target, so return the index.
        if middle_value == target_value:
            return middle_index

        # Target is in the left half.
        if target_value < middle_value:
            right_index = middle_index - 1

        # Target is in the right half.
        else:
            left_index = middle_index + 1

    # Target not found in the list.
    return -1

Big(O) Analysis

Time Complexity

O(log n) – Binary search operates on a sorted input array of size n. With each comparison, the search space is halved. The algorithm continues until the target is found or the search space is exhausted. The number of iterations required is proportional to the number of times n can be divided by 2 until it reaches 1, which is log base 2 of n. Thus, the time complexity is O(log n).

Space Complexity

O(1) – The binary search algorithm, as described, only uses a few constant extra variables such as pointers or indices to keep track of the search space boundaries. No additional data structures that scale with the input size (N) are created. The memory usage remains constant regardless of the size of the input array, where N is the number of elements in the sorted list. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as binary search cannot operate on an empty or null array.
Array with one element	Return -1 as the element either matches or doesn't match the target.
Target value less than the smallest element in the sorted array	Binary search will converge to the first element, mid < target always, and return -1.
Target value greater than the largest element in the sorted array	Binary search will converge to the last element, mid > target always, and return -1.
Target value equals the first element of the array	The algorithm should correctly find the target at index 0.
Target value equals the last element of the array	The algorithm should correctly find the target at index array.length -1.
Array contains duplicate target values	Binary search may return any one of the indices where the target is found, but the question probably expects just ANY match.
Integer overflow when calculating mid = (low + high) / 2	Use mid = low + (high - low) / 2 to prevent potential integer overflow in languages like Java or C++.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input array guaranteed to be sorted in ascending order?
Can the target value appear multiple times in the array, and if so, which index should I return (e.g., the first occurrence)?
What should I return if the target value is not found in the array?
Can the input array be empty?
What is the range of possible values in the array and for the target?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very first item in the list.
Check if that item is the thing you're searching for.
If it's not, move to the next item in the list.
Repeat this process of checking each item until you either find the item you're looking for or you reach the end of the list.
If you reach the end of the list without finding the item, it means the item is not in the list.

Code Implementation

def linear_search(sorted_list, target_value):
    list_length = len(sorted_list)

    # Iterate through each element in the sorted list.
    for current_index in range(list_length):
        current_element = sorted_list[current_index]

        # Check if the current element matches the target.
        if current_element == target_value:
            return current_index

        # Exit early if we surpass the target, due to list being sorted
        if current_element > target_value:
            return -1

    # Return -1 if target isn't found after checking all elements.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the middle value of the list.
If the middle value is what you're looking for, you're done!
If the value you're looking for is less than the middle value, you know it must be in the first half of the list. So, discard the second half and repeat the process on the first half.
If the value you're looking for is greater than the middle value, you know it must be in the second half of the list. Discard the first half and repeat the process on the second half.
Keep repeating this 'divide and conquer' approach until you find the value or the list becomes empty. If the list becomes empty, the value is not in the list.

Code Implementation

def binary_search(sorted_list, target_value):
    left_index = 0
    right_index = len(sorted_list) - 1

    while left_index <= right_index:
        middle_index = (left_index + right_index) // 2
        middle_value = sorted_list[middle_index]

        # Found the target, so return the index.
        if middle_value == target_value:
            return middle_index

        # Target is in the left half.
        if target_value < middle_value:
            right_index = middle_index - 1

        # Target is in the right half.
        else:
            left_index = middle_index + 1

    # Target not found in the list.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as binary search cannot operate on an empty or null array.
Array with one element	Return -1 as the element either matches or doesn't match the target.
Target value less than the smallest element in the sorted array	Binary search will converge to the first element, mid < target always, and return -1.
Target value greater than the largest element in the sorted array	Binary search will converge to the last element, mid > target always, and return -1.
Target value equals the first element of the array	The algorithm should correctly find the target at index 0.
Target value equals the last element of the array	The algorithm should correctly find the target at index array.length -1.
Array contains duplicate target values	Binary search may return any one of the indices where the target is found, but the question probably expects just ANY match.
Integer overflow when calculating mid = (low + high) / 2	Use mid = low + (high - low) / 2 to prevent potential integer overflow in languages like Java or C++.