Binary Search

You are given an m x n integer matrix matrix and an integer target. Return True if target is in the matrix; otherwise, return False. The matrix satisfies two conditions: Every row is sorted in non-decreasing order. The first integer of each row is strictly greater than the last integer of the previous row. The required time complexity is O(log(m * n)). For example, consider this matrix: 1 3 5 7 10 11 16 20 23 30 34 60 When target = 3, return True. When target = 13, return False. The constraints are: ...

Problem Requirement The input is a non-empty integer array nums. Every element is unique, and before rotation the array was sorted in strictly increasing order. The array is rotated between 1 and nums.length times. One rotation moves the last element to the front; therefore, nums.length rotations restore the original increasing order. Return the minimum value in the rotated array. The problem requires an algorithm with O(log n) runtime. LeetCode uses this method contract: ...

Problem Requirement The input gives an integer array nums and an integer target. Every value in nums is distinct, and the array was strictly increasing before rotation. Before the method is called, it may be rotated at an unknown index k (0 <= k < nums.length) into: [nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]] Return the index of target in the rotated array when it exists; otherwise return -1. The problem requires an algorithm with O(log n) runtime. ...

Subtitle / Summary This problem is a useful bridge between sorting and binary search. After sorting the array, all copies of target become one contiguous block, and the answer is simply every index inside that block. Reading time: 10-12 min Tags: sorting, binary search, range location SEO keywords: Find Target Indices After Sorting Array, LeetCode 2089, lower bound, upper bound Meta description: Sort the array, use lower and upper bounds to find the target block, and return every matching index, with tradeoffs, engineering scenarios, and runnable implementations in six languages. Target Readers Learners connecting sorting with lower/upper bound search Engineers who need all positions of one value after offline sorting Interview candidates reviewing how contiguous blocks form in sorted data Background / Motivation The input array is not sorted, so we cannot apply binary search immediately. But once we sort it, every copy of the same value becomes one continuous segment. ...

Subtitle / Summary This problem is a compact exercise in boundary counting. Because the array is already sorted, you do not count negatives and positives one by one; you find where zero starts and where zero ends, then compute both counts from those boundaries. Reading time: 10-12 min Tags: binary search, counting, sorted array, boundaries SEO keywords: Maximum Count of Positive Integer and Negative Integer, LeetCode 2529, boundary counting Meta description: Use lower-bound and upper-bound binary search around zero to count negatives and positives in a sorted array, with correctness reasoning, engineering scenarios, and runnable implementations in six languages. Target Readers Learners practicing boundary search beyond exact-match lookup Engineers who count segments in sorted data Interview candidates learning how lower and upper bounds produce counts Background / Motivation The input is already sorted. That changes the problem completely. ...

Problem Requirement Start with the official input nums = [5,7,7,8,8,10] and target = 8. The answer must be the complete range [3,4]; returning only index 3 or 4 does not identify both the target’s first and last occurrences. Given an integer array nums sorted in non-decreasing order and an integer target: If target exists, return the indices of its first and last occurrences as [first, last]. If target does not exist, return [-1, -1]. The problem ultimately requires an algorithm with O(log n) runtime. LeetCode uses this method contract: ...

Subtitle / Summary Search Insert Position is the cleanest lower-bound problem in LeetCode. If you can reliably find the first index where nums[i] >= target, you already have the core template for insert positions, range starts, and many boundary-search problems. Reading time: 10-12 min Tags: binary search, lower bound, sorted array SEO keywords: Search Insert Position, lower bound, binary search, LeetCode 35 Meta description: Lower-bound binary search for Search Insert Position, with boundary reasoning, pitfalls, engineering scenarios, and runnable implementations in Python, C, C++, Go, Rust, and JavaScript. Target Readers Learners who know basic binary search but still hesitate on boundary handling Engineers who insert or locate values in sorted tables Interview candidates who want one reusable lower-bound template Background / Motivation This problem looks simple because the output is a single index. The real lesson is deeper: ...

Subtitle / Summary This problem is a textbook upper-bound search with one extra twist: wrap-around. Once you can find the first character > target, the rest is just handling the “no answer inside the array” case by returning the first element. Reading time: 10-12 min Tags: binary search, upper bound, characters, wrap-around SEO keywords: Find Smallest Letter Greater Than Target, upper bound, LeetCode 744 Meta description: Use upper-bound binary search and wrap-around handling to solve LeetCode 744, with correctness reasoning, pitfalls, engineering scenarios, and runnable code in six languages. Target Readers Learners who already know lower bound and want to master upper bound Engineers who search the next greater value in a sorted cyclic list Interview candidates practicing boundary-style binary search Background / Motivation At first glance, this looks like a character problem. It is actually a boundary problem: ...