We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Search

Number: 792

Difficulty: Easy

Paid? No

Companies: Google, Meta, Bloomberg, Microsoft, Oracle, Amazon, Apple, Adobe, Yandex

Problem Description

(A short summary or question text)

Key Insights

  • Utilize binary search to achieve O(log n) runtime on a sorted array.
  • Use two pointers to maintain the current search region.
  • Narrow down the search range by comparing the middle element with the target.
  • Return the index when the target is found; otherwise, return -1 if not found.

Space and Time Complexity

Time Complexity: O(log n) Space Complexity: O(1)

Solution

We use an iterative binary search algorithm. We initialize two pointers, left and right, to represent the current segment of the array that could contain the target. At each iteration, we compute the middle index and compare the element there with the target. If they match, we return the index. Otherwise, based on whether the target is smaller or larger than the middle element, we adjust our pointers to narrow the search to either the left or right half of the array. This process continues until the target is found or until the pointers cross, indicating that the target is not present. No extra data structures are used, making the space complexity O(1).

Code Solutions

# Python code for binary search

def search(nums, target):
    # Set initial boundaries for the search
    left, right = 0, len(nums) - 1
    
    # Loop until the search space is empty
    while left <= right:
        # Calculate middle index to avoid overflow
        mid = left + (right - left) // 2
        
        # Check if the mid element matches the target
        if nums[mid] == target:
            return mid
        # If target is smaller than mid element, narrow search to left half
        elif target < nums[mid]:
            right = mid - 1
        # Else, narrow search to right half
        else:
            left = mid + 1
    
    # Target not found, return -1
    return -1

# Example usage:
print(search([-1,0,3,5,9,12], 9))  # Expected output: 4
← Back to All Questions