Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Binary Search solution and explanation

EasyArrayBinary Search5 min read61.2% acceptanceUpdated 9 Apr 2026
Asked atMetaPure StorageGoogleAmazonMicrosoftBloomberg
+5 moreInfosysCognizantOracleTCSYandex
Practise Binary Search
9:40
Binary Search - Leetcode 704 - PythonNeetCode · 9:40 · 267K viewsWatch on YouTube
9 more videos on this problem
  1. Binary Search - Leetcode 704 - PythonNeetCode · 9:40 · 267K views
  2. Binary Search - Leetcode 704 - Binary Search (Python)Greg Hogg · 6:22 · 15K views
  3. Leetcode | 704. Binary Search | Easy | Java SolutionDeveloper Docs · 6:13 · 3K views
  4. 704 Binary Search LeetCode (Google Interview Question) JavaScriptdev alex · 6:35 · 2K views
  5. Binary Search - LeetCode 704 - JavaScriptAlgoJS · 4:01 · 2K views
  6. Binary Search | Leet code 704 | Theory explained + Python codeSai Anish Malla · 9:59 · 2K views
  7. Binary Search - LeetCode #704 with python programmingCodingNinja · 7:15 · 1K views
  8. LeetCode 704 - Binary Search - C++iamdriy · 5:09 · 731 views
  9. LeetCode 704. Binary Search - Interview Prep Ep 136Fisher Coder · 11:25 · 696 views
  10. LeetCode#704 Binary Search - PythonCodeJulian · 1:01 · 675 views

The problem

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 <= 104
  • -104 < nums[i], target < 104
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Approach overview

Problem Overview: Given a sorted integer array nums and a target, return the index of the target if it exists. If the value is not present, return -1. The key constraint is that the array is already sorted, which allows you to use binary search instead of scanning every element.

Approach 1: Linear Scan (Brute Force) (Time: O(n), Space: O(1))

The most direct approach is to iterate through the array from left to right and compare every element with target. The moment you find a match, return its index. If the loop finishes without finding the value, return -1. This works for any array, sorted or not, but it ignores the sorted property entirely. Each lookup may require scanning the entire array, so the time complexity grows linearly with n.

Approach 2: Iterative Binary Search (Time: O(log n), Space: O(1))

Binary search cuts the search space in half on every step. Start with two pointers: left = 0 and right = n - 1. Compute the middle index using mid = left + (right - left) / 2 to avoid overflow. If nums[mid] == target, return mid. If the middle value is smaller than the target, discard the left half by setting left = mid + 1. Otherwise discard the right half with right = mid - 1. Continue until the pointers cross. Because the search space halves each iteration, the time complexity is O(log n) and the algorithm uses O(1) extra space.

This iterative form is the most common implementation in production code. It avoids recursion overhead and keeps memory usage constant. Many interviewers prefer this version because it shows clear pointer control and correct boundary handling.

Approach 3: Recursive Binary Search (Time: O(log n), Space: O(log n))

The same halving logic can be expressed recursively. Define a function that takes left and right boundaries. Compute mid, compare with the target, and recursively search either the left or right half. The recursion stops when left > right. Each recursive call reduces the problem size by half, so the time complexity remains O(log n). However, recursion adds call stack overhead, giving it O(log n) auxiliary space.

This version is easier to reason about conceptually because the code mirrors the divide-and-conquer idea directly. It is also a good demonstration of recursion, though most engineers switch to the iterative version in performance-sensitive code.

Recommended for interviews: Iterative binary search is the expected solution. It demonstrates that you recognize the sorted array property and can reduce the search space efficiently to O(log n). Mentioning the linear scan shows baseline understanding, but implementing binary search correctly—especially pointer updates and midpoint calculation—demonstrates real algorithmic skill.

Approach 1: Iterative Binary Search

The iterative binary search approach involves using a loop to divide the array into halves repeatedly until the target is found or the search range is empty. This approach utilizes two pointers, 'low' and 'high', that represent the current search bounds.

def binary_search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [-1, 0, 3, 5, 9, 12]
target = 9
print(binary_search(nums, target))
class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        System.out.println(sol.search(nums, target));
    }
}
#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int low = 0, high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    int result = binarySearch(nums, target);
    std::cout << result << std::endl;
    return 0;
}
function binarySearch(nums, target) {
    let low = 0, high = nums.length - 1;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (nums[mid] === target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

const nums = [-1, 0, 3, 5, 9, 12];
const target = 9;
console.log(binarySearch(nums, target));
#include <stdio.h>

int binarySearch(int* nums, int numsSize, int target) {
    int low = 0, high = numsSize - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

int main() {
    int nums[] = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    int result = binarySearch(nums, 6, target);
    printf("%d\n", result);
    return 0;
}
using System;

public class Solution {
    public int Search(int[] nums, int target) {
        int low = 0, high = nums.Length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        Console.WriteLine(sol.Search(nums, target));
    }
}

This Python solution iteratively narrows down the search space using the 'low' and 'high' pointers to perform binary search.

Complexity

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

Try this approach in the editor

Approach 2: Recursive Binary Search

The recursive binary search involves calling a function that repeatedly calls itself with updated bounds until the target is found or the bounds overlap. This approach provides a cleaner implementation at the cost of additional space used by the call stack.

def binary_search_rec(nums, low, high, target):
    if low > high:
        return -1
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_rec(nums, mid + 1, high, target)
    else:
        return binary_search_rec(nums, low, mid - 1, target)

nums = [-1, 0, 3, 5, 9, 12]
target = 9
print(binary_search_rec(nums, 0, len(nums) - 1, target))
class Solution {
    public int binarySearchRec(int[] nums, int low, int high, int target) {
        if (low > high) return -1;
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) return binarySearchRec(nums, mid + 1, high, target);
        return binarySearchRec(nums, low, mid - 1, target);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        System.out.println(sol.binarySearchRec(nums, 0, nums.length - 1, target));
    }
}
#include <iostream>
#include <vector>

int binarySearchRec(const std::vector<int>& nums, int low, int high, int target) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) return binarySearchRec(nums, mid + 1, high, target);
    return binarySearchRec(nums, low, mid - 1, target);
}

int main() {
    std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    int result = binarySearchRec(nums, 0, nums.size() - 1, target);
    std::cout << result << std::endl;
    return 0;
}
function binarySearchRec(nums, low, high, target) {
    if (low > high) return -1;
    let mid = Math.floor((low + high) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) return binarySearchRec(nums, mid + 1, high, target);
    return binarySearchRec(nums, low, mid - 1, target);
}

const nums = [-1, 0, 3, 5, 9, 12];
const target = 9;
console.log(binarySearchRec(nums, 0, nums.length - 1, target));
#include <stdio.h>

int binarySearchRec(int* nums, int low, int high, int target) {
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) return binarySearchRec(nums, mid + 1, high, target);
    return binarySearchRec(nums, low, mid - 1, target);
}

int main() {
    int nums[] = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    int result = binarySearchRec(nums, 0, 5, target);
    printf("%d\n", result);
    return 0;
}
using System;

public class Solution {
    public int BinarySearchRec(int[] nums, int low, int high, int target) {
        if (low > high) return -1;
        int mid = low + (high - low) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) return BinarySearchRec(nums, mid + 1, high, target);
        return BinarySearchRec(nums, low, mid - 1, target);
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        Console.WriteLine(sol.BinarySearchRec(nums, 0, nums.Length - 1, target));
    }
}

This Python implementation of recursive binary search updates 'low' and 'high' recursively, ending when the target is detected or ruled out.

Complexity

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

Try this approach in the editor

Approach 3: Binary Search

We define the left boundary l=0 and the right boundary r=n-1 for binary search.

In each iteration, we calculate the middle position mid=(l+r)/2, then compare the size of nums[mid] and target.

  • If nums[mid] geq target, it means target is in the left half, so we move the right boundary r to mid;
  • Otherwise, it means target is in the right half, so we move the left boundary l to mid+1.

The loop ends when l<r, at this point nums[l] is the target value we are looking for. If nums[l]=target, return l; otherwise, return -1.

The time complexity is O(log n), where n is the length of the array nums. The space complexity is O(1).

function search(nums: number[], target: number): number {
    let [l, r] = [0, nums.length - 1];
    while (l < r) {
        const mid = (l + r) >> 1;
        if (nums[mid] >= target) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return nums[l] === target ? l : -1;
}
func search(nums []int, target int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := (l + r) >> 1
		if nums[mid] >= target {
			r = mid
		} else {
			l = mid + 1
		}
	}
	if nums[l] == target {
		return l
	}
	return -1
}
impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut l: usize = 0;
        let mut r: usize = nums.len() - 1;
        while l < r {
            let mid = (l + r) >> 1;
            if nums[mid] >= target {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if nums[l] == target {
            l as i32
        } else {
            -1
        }
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Iterative Binary Search

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

Recursive Binary Search

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

Binary Search–

Complexity analysis

ApproachTimeSpaceWhen to Use
Linear ScanO(n)O(1)When the array is unsorted or simplicity matters more than performance
Iterative Binary SearchO(log n)O(1)Best choice for sorted arrays and interview solutions
Recursive Binary SearchO(log n)O(log n)When demonstrating divide-and-conquer or recursion patterns

Frequently asked questions

Is Binary Search easy or hard?

Binary search is classified as an easy problem on most coding platforms, but many candidates make mistakes with boundary updates or midpoint calculation. The concept is simple—halve the search space—but implementing it correctly and avoiding off-by-one errors requires practice.

Binary Search Python/Java solution

In Python or Java, implement binary search using two pointers and a loop. Compute the midpoint, compare with the target, and shrink the search range accordingly. Both languages achieve O(log n) time and O(1) space with the iterative implementation.

How to solve Binary Search in O(log n)?

Use the sorted property of the array. Maintain two pointers, left and right, compute the midpoint, and compare nums[mid] with the target. If the target is larger, move the left pointer to mid + 1; otherwise move the right pointer to mid - 1. Repeating this halving process reduces the search space exponentially, resulting in O(log n) time.

What is the best approach for Binary Search?

Iterative binary search is the best approach for this problem. It repeatedly halves the search range using two pointers and a midpoint check, achieving O(log n) time complexity with O(1) space. The iterative version avoids recursion overhead and is the most commonly expected implementation in interviews.

Is Binary Search asked at Google/Amazon/Meta?

Binary search is a fundamental algorithm frequently used in interviews at companies like Google, Amazon, and Meta. It often appears directly or as part of variations such as searching in rotated arrays, finding boundaries, or determining insertion positions in sorted data.

What data structure is used in Binary Search?

Binary search operates on a sorted array or any random-access structure that allows constant-time index lookup. Arrays are the most common structure because they support direct indexing, which is required to quickly access the midpoint during each step.

What is the time complexity of Binary Search?

Binary search runs in O(log n) time because the search space is cut in half after each comparison. For an array of size n, the algorithm performs at most log2(n) iterations. Space complexity is O(1) for the iterative version and O(log n) for the recursive version due to the call stack.

Comments

Next problem · similarSearch in a Sorted Array of Unknown SizeMedium
Now write it yourselfClose this page and solve Binary Search in the editor, without looking.
Practise Binary Search