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.

Description Solution Video 9:40

704. Binary Search

Easy61.2% acceptance11 companies

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.

Asked at 11 companies

Meta Pure Storage

Google Amazon Microsoft Bloomberg

Infosys Cognizant Oracle

TCS Yandex

Topics

Array Binary Search

9:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

704. Binary Search

Asked at 11 companies

Topics

Similar problems