← all entries
A-028● Day 282026.06.03easyleetcode #704neetcode150

Binary Search

#array#binary-search
↗ leetcode #704 · binary-search
01

Problem

· problem
P.028

Binary Search

↗ leetcode #704

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.

constraints
  • · 1 ≤ nums.length ≤ 10⁴
  • · -10⁴ < nums[i], target < 10⁴
  • · All integers in nums are unique
  • · nums is sorted in ascending order
// paraphrased summary — see source for full text
examples
example 1input → output
[-1,0,3,5,9,12]
9
4
example 2input → output
[-1,0,3,5,9,12]
2
-1
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Is the return value 0-based indexing?
  • ☐
    What should be returned if the target is not in the array?
  • ☐
    What does the O(log n) complexity requirement imply?
  • ☐
    Can the array contain duplicate values?
  • ☐
    Do we need to sort the array first?
  • ☐
    Is linear search (checking every element) acceptable?
  • ☐
    Should we return all indices where the target appears?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize Pointers
○
l, r = 0, len(nums) - 1
○
l, r = 0, len(nums)
○
l, r = 1, len(nums) - 1
step 2· Loop Condition
○
while l <= r:
○
while l < r:
○
while l <= r and nums[l] != target:
step 3· Calculate Middle Index│ nested
○
m = l + ((r - l) // 2)  # (l + r) // 2 can lead to overflow
○
m = (l + r) // 2
○
m = (r - l) // 2
step 4· If Middle > Target, Search Left│ nested
○
if nums[m] > target:
○
if nums[m] >= target:
○
if nums[m] > target: l = m + 1
step 5· If Middle < Target, Search Right│ nested
○
elif nums[m] < target:
○
elif nums[m] < target: r = m - 1
○
elif nums[m] <= target:
step 6· Return Result
○
else:
○
else: return -1
○
if nums[m] == target: return m
else: continue
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        l, r = 0, len(nums) - 1
4
5
        while l <= r:
6
            m = l + ((r - l) // 2)  # (l + r) // 2 can lead to overflow
7
            if nums[m] > target:
8
                r = m - 1
9
            elif nums[m] < target:
10
                l = m + 1
11
            else:
12
                return m
13
        return -1
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
[-1,0,3,5,9,12]
9
→
4
case 2
[-1,0,3,5,9,12]
2
→
-1
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.