GL
GrindLens
PatternsSheetsPricingQuestions
  1. Home
  2. /Patterns
  3. /Binary Search (Classic Lookup)
←All Patterns
Binary SearchEvidence Contributing

Binary Search (Classic Lookup)

Standard binary search over a sorted array (or a local monotonic comparison) to locate a target index or boundary.

Practice Problems: 7
Difficulty: 2 Easy·4 Medium·1 Hard

Core technique

Halve the search range each step by checking the middle element. Sorted order tells you which half cannot contain the target, so n elements take about log2 n comparisons.

How to recognize it

  • The input is sorted, or some property flips from false to true at a single point.
  • The problem asks for a target position, an insertion index, or the first or last position where something holds.
  • The required time is O(log n), or n is large enough that a linear scan is too slow.
  • You can tell which half to keep from the middle element alone.

Template

This is the closed-interval version. The search range is left to right inclusive, so the loop runs while left <= right and both bounds move past mid. Compute mid as left + (right - left) / 2 so the sum cannot overflow.

Python

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

Java

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

JavaScript

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

Worked example: Search Insert Position

  1. For a strictly increasing array, return the target index or its insertion index. Use the same loop, but return left instead of -1 when it ends. With duplicates, this exact-match template is not a lower-bound search and may return any matching index.
  2. Take nums = 1, 3, 5, 6 and target = 2. Start with left = 0 and right = 3.
  3. mid = 1 holds 3, which is larger than 2, so right becomes 0.
  4. Now left = 0 and right = 0. mid = 0 holds 1, which is smaller than 2, so left becomes 1.
  5. left is greater than right, so the loop stops. left = 1 is exactly where 2 belongs.
  6. Why left is the insertion point: every index before left holds a value smaller than the target, and every index from left onward holds a larger one.

Complexity: O(log n) time and O(1) space.

Try Search Insert Position on LeetCode↗

Common mistakes

  • Writing left = mid or right = mid with a closed interval, which can loop forever. Move past mid with mid + 1 or mid - 1.
  • Mixing conventions. With a half-open interval (right starts at n) the loop is left < right and right = mid. Pick one convention and keep the loop condition and both updates consistent with it.
  • Computing mid as (left + right) / 2 in Java or C++, where the sum can overflow.
  • Forgetting the empty array. right starts at -1, the loop never runs, and you must return the not-found value or insertion index 0.
  • Running it on data that is not sorted. The result is silently wrong rather than an error.

When this pattern does not fit

  • The data is unsorted and you only need one lookup. One linear scan costs less than sorting first.
  • There is no monotonic property to split on, so the middle element tells you nothing about either half.
  • You need membership checks across many lookups. A hash set gives O(1) lookups after a single build.

Canonical Practice Problems

7 problems
1.Binary SearchEasy
Solve on LeetCode↗
2.Search Insert PositionEasy
Solve on LeetCode↗
3.Find First and Last Position of Element in Sorted ArrayMedium
Solve on LeetCode↗
4.Find Peak ElementMedium
Solve on LeetCode↗
5.Search a 2D MatrixMedium
Solve on LeetCode↗
6.Time Based Key Value StoreMedium
Solve on LeetCode↗
7.Minimum Interval to Include Each QueryHard
Solve on LeetCode↗

Curated Sheets Containing This Pattern

NeetCode All

7 problems

→

Striver A2Z

5 problems

→

LeetCode Top Interview 150

4 problems

→

NeetCode 150

4 problems

→

Love Babbar 450

1 problem

→

Striver SDE Sheet

1 problem

→

Related Algorithmic Patterns

Heap1 shared

Heap for Top-K / Kth Element

Binary Search

Binary Search on a Rotated Array

Binary Search

Binary Search on the Answer

GL
GrindLens

Precision pattern analytics and curated sheet tracking for algorithmic coding interview preparation.

Quick lookup:⌘Kor/

Platform

  • Patterns→
  • Sheets→
  • Pricing→

Community

  • Feedback
  • Report a bug
  • X
  • LinkedIn

© 2026 GrindLens. LeetCode is a trademark of LeetCode. GrindLens is an independent analytics platform and is not affiliated with or endorsed by LeetCode.

Terms of ServicePrivacy Policy