Location>code7788 >text

1. Two points

Popularity：736 ℃/2025-04-13 18:55:36

0. Reference materials (explained videos and blogs, etc.)

  • Video tutorial
    • Bilibili: The dichotomy of the algorithm (with analysis of LeetCode real questions)
    • LeetCode official: The essence of dichotomy and code template
    • [【Algorithm Exquisite Series】Basic Algorithm: Dichotomy | Say goodbye to the dead loop from now on]/video/BV11A411R7BK?vd_source=d40f68483c8501ae1703de6cc0b5b7d1
    • 【Binary search for red and blue staining method】/video/BV1AP41137w7/?share_source=copy_web&vd_source=d40f68483c8501ae1703de6cc0b5b7d1
  • Blog Analysis
    • Zhihu Highly praised: 11 variant scenarios of dichotomy and guide to avoid pits
    • [Special topic of "Code Random Thoughts"](/0704. Binary search.html)

1. Application scenarios

  1. OrderlyData query
    • Quickly locate target values ​​in sorted arrays/linked lists (such as database index query)
  2. Boundary value detection
    • Find the first/last element that satisfies the condition (such as IP address home match)
  3. Numerical calculation optimization
    • Find square root and logarithmic approximation (can be combined with Newton's iterative method)
  4. Monotonic function extreme value
    • Find peaks and valleys (such as the best time to buy and sell stocks)
  5. Questions with limited scope of answers
    • The optimal solution is approached by two parts within the possible solution range (such as cake splitting problem, Koko eating banana problem)

2. Core ideas/steps

  1. Core idea
    • Half apart: Optimize linear search to logarithmic level by continuously narrowing the candidate interval
    • Loop invariant: Maintain the consistency of interval definition (left and right closed[left, right]Or close left and open right[left, right)）
  2. General steps
a. Initialize the left and right boundaries (need to cover all possible solutions)
 b. while(left ≤ right):
      i. Calculate mid = left + (right - left)/2 // Prevent overflow
      ii. Select the left or right half interval according to the mid value and the target relationship
 c. Return the final index or boundary value
  1. Key details
    • Termination conditions：left > rightEnd the loop
    • Boundary update：
      • Find the exact value:left = mid + 1orright = mid - 1
      • Find the left border:right = mid(Close left and open right)
      • Find the right border:left = mid + 1

3. Code templates and tests

Code template (java as an example)

// Basic template: Find target value (array ascending)
 public int binarySearch(int[] nums, int target) {
 int left = 0, right = - 1;
 while (left <= right) {
 int mid = left + (right - left) / 2;
 if (nums[mid] == target) return mid;
         else if (nums[mid] < target) left = mid + 1;
         else right = mid - 1;
     }
 return -1;
 }
 // Variety template: look for the left border (such as LeetCode 34)
 public int findLeftBound(int[] nums, int target) {
 int left = 0, right = ;   // Open right interval
 while (left < right) {
 int mid = left + (right - left) / 2;
 if (nums[mid] >= target) right = mid;
         else left = mid + 1;
     }
 return (left <  && nums[left] == ​​target) ? left : -1;
 }

Sample

Sample question: LeetCode 704. Binary search

class Solution {
    public int search(int[] nums, int target) {
        int l = 0,r = -1;
        while(l<=r){
            int mid = (l+r)>>1;
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]<target){
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        return -1;
    }
}

4. Optimization and similar algorithms

Optimization solution

  1. Computational Optimization
    • Use bit operations instead of division:mid = (left + right) >> 1(Java unsigned right shift)
  2. Unified interval definition
    • Always use the left-closed and right-open interval to reduce boundary conditions judgment
  3. Terminate early
    • When the data volume is extremely large, add pruning logic to end the interval that cannot produce the expected solution beforehand

Algorithm comparison/complexity analysis

algorithm Time complexity Space complexity Applicable scenarios
dichotomy O(log n) O(1) Ordered data or implicit monotonic functions
Linear Scan O(n) O(1) Disordered small-scale data
Hash table O(1) O(n) Frequent query but no scope operation is required

5. Recommended related topics

  1. Basic Applications
    • 35. Search for insertion location
    • 374. Guess the size of the number
  2. Boundary variant
    • 34. Find the first and last positions of elements in a sorted array
    • 278. The first wrong version
  3. Abstract model
    • 153. Find the minimum value in a rotating sorted array
    • 875. Koko, who loves bananas
  4. Advanced
  • 74. Search for two-dimensional matrix - LeetCode
  • 410. The maximum value of split array - LeetCode
  • 1819. Number of different greatest common divisors in a sequence - LeetCode
<Previous Next>