Binary Search

Easy

Given a sorted array of integers nums and a target value, return the index of target if it is in nums, otherwise return -1. You must write an algorithm with O(log n) runtime complexity.

Examples

InputOutput
nums = [-1,0,3,5,9,12], target = 94
nums = [-1,0,3,5,9,12], target = 2-1

Python Solution

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

JavaScript Solution

function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Step-by-Step Explanation

  1. Maintain left and right boundaries of the search space.
  2. Compute mid index and compare with target.
  3. If equal, return mid. If target is larger, search right half; else search left half.
  4. Repeat until left > right, then return -1.

Complexity Analysis

TimeO(log n)
SpaceO(1)

Tags

ArrayBinary Search

Related Problems

Merge Two Sorted ArraysRemove Duplicates from Sorted Array

Related Tools

JSON Formatter

All Problems

Two SumReverse a StringPalindrome CheckFizzBuzzReverse Linked ListMerge Two Sorted ArraysValid ParenthesesMaximum Subarray (Kadane's Algorithm)Remove Duplicates from Sorted ArrayNth Fibonacci NumberValid AnagramFirst Unique CharacterClimbing StairsRoman to IntegerBest Time to Buy and Sell StockContains DuplicateMove ZeroesIntersection of Two ArraysLongest Common Prefix