Skip to content

Binary Search

[ ]

()

[)

->

\(\geq\)

\(>\)

\(<\)

\(\leq\)

  1. sorted

704. Binary Search

TC: \(O(log_2(n))\)

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return -1;
        }

        int left = 0;
        int right = nums.length -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;

    }
}

35. Search Insert Position

162. Find Peak Element

74

Binary Search Problems

  • 34.Find First and Last Position of Element in Sorted Array
  • 35.Search Insert Position
  • 704.Binary Search
  • 744.Find Smallest Letter Greater Than Target
  • 2529.Maximum Count of Positive Integer and Negative Integer
  • 1385.Find the Distance Value Between Two Arrays
  • 2300.Successful Pairs of Spells and Potions
  • 2389.Longest Subsequence With Limited Sum
  • 1170.Compare Strings by Frequency of the Smallest Character
  • 2080.Range Frequency Queries
  • 2563.Count the Number of Fair Pairs
  • 2856.Minimum Array Length After Pair Removals
  • 981.Time Based Key-Value Store
  • 1146.Snapshot Array
  • 658.Find K Closest Elements
  • 1818.Minimum Absolute Sum Difference
  • 911.Online Election
  • LCP 08.Trigger Time
  • 1150.Check If a Number Is Majority Element in a Sorted Array (Premium)
  • 1064.Fixed Point (Premium)
  • 702.Search in a Sorted Array of Unknown Size (Premium)
  • 1182.Shortest Distance to Target Color (Premium)
  • 2819.Minimum Relative Loss After Buying Chocolates (Premium)
  • 2936.Count Equal Value Blocks (Premium)

Binary Search: Find Minimum

  • 1283.Find the Smallest Divisor Given a Threshold
  • 2187.Minimum Time to Complete Trips
  • 1870.Minimum Speed to Arrive on Time
  • 1011.Capacity to Ship Packages Within D Days
  • 875.Koko Eating Bananas
  • 3296.Minimum Seconds to Move Mountains
  • 475.Heaters
  • 2594.Minimum Time to Repair Cars
  • 1482.Minimum Days to Make m Bouquets
  • 3048.Earliest Time to Mark All Indices I
  • 3049.Earliest Time to Mark All Indices II
  • 2604.Shortest Time to Eat All Barley (Premium)
  • 2702.Minimum Operations to Make Numbers Non-Positive (Premium)

Binary Search: Find Maximum

  • 275.H-Index II
  • 2226.Maximum Candies Allocated to K Children
  • 2982.Find the Longest Special Substring Appearing at Least Three Times II
  • 2576.Maximum Number of Marked Indices
  • 1898.Maximum Number of Removable Characters
  • 1802.Maximum Value at a Given Index in a Bounded Array
  • 1642.Furthest Building You Can Reach
  • 2861.Maximum Number of Alloys
  • 3007.Maximum Number with Value and Sum Less Than or Equal to K
  • 2141.Maximum Running Time of N Computers
  • 2258.Escape the Fire
  • 2071.Maximum Number of Tasks You Can Assign
  • 1618.Find the Largest Font Size That Fits (Premium)
  • 1891.Cut Ropes (Premium)
  • 2137.Equalize Water Levels by Pouring Operations (Premium)
  • 644.Maximum Average Subarray II (Premium)

Binary Search: Indirect Values

  • 3143.Maximum Points in a Square
  • 1648.Sell Diminishing-Valued Colored Balls

Minimize the Maximum Value

  • 410.Split Array Largest Sum
  • 2064.Minimize Maximum of Products Distributed to Stores
  • 1760.Minimum Limit of Balls in a Bag
  • 1631.Minimum Effort Path
  • 2439.Minimize Maximum Value in Array
  • 2560.House Robber IV
  • 778.Swim in Rising Water
  • 2616.Minimize the Maximum Difference of Pairs
  • 2513.Minimize the Maximum Value of Two Arrays
  • LCP 12.Xiao Zhang's Reading Plan
  • 774.Minimize Maximum Distance to Gas Station (Premium)

Maximize the Minimum Value

  • 3281.Maximum Score of an Integer in Range
  • 2517.Maximum Tastiness of Candy Basket
  • 1552.Magnetic Force Between Two Balls
  • 2812.Find the Safest Path
  • 2528.Maximize the Minimum Power of a City
  • 1102.Path with Maximum Minimum Value (Premium)
  • 1231.Divide Chocolate (Premium)

Kth Smallest/Largest

  • 378.Kth Smallest Element in a Sorted Matrix
  • 668.Kth Smallest Number in Multiplication Table
  • 719.Find K-th Smallest Pair Distance
  • 878.Nth Magical Number
  • 1201.Ugly Number III
  • 793.Preimage Size of Factorial Zeroes Function
  • 373.Find K Pairs with Smallest Sums
  • 1439.Kth Smallest Sum of a Matrix with Sorted Rows
  • 786.K-th Smallest Prime Fraction
  • 3116.Kth Smallest Value with Single-Sided Denominations
  • 3134.Find the Median of Uniqueness Arrays
  • 2040.K-th Smallest Product of Two Sorted Arrays
  • 2386.Kth Largest Sum in a Subarray
  • 1508.Range Sum of Sorted Subarray Sums
  • 1918.K-th Smallest Subarray Sum (Premium)

Other Binary Search Problems - [ ] 69.Sqrt(x) - [ ] 74.Search a 2D Matrix - [ ] 240.Search a 2D Matrix II - [ ] 2476.Closest Nodes Queries in a Binary Search Tree - [ ] 278.First Bad Version - [ ] 374.Guess Number Higher or Lower - [x] 162.Find Peak Element - [x] 1901.Find a Peak Element II - [ ] 852.Peak Index in a Mountain Array - [ ] 1095.Find in Mountain Array - [x] 153.Find Minimum in Rotated Sorted Array - [x] 33.Search in Rotated Sorted Array - [ ] 222.Count Complete Tree Nodes - [ ] 1539.Kth Missing Positive Number - [ ] 540.Single Element in a Sorted Array - [ ] 4.Median of Two Sorted Arrays - [ ] 1060.Missing Element in Sorted Array (Premium) - [ ] 1198.Find Smallest Common Element in All Rows (Premium) - [ ] 1428.Leftmost Column with at Least a One (Premium) - [ ] 1533.Find the Index of the Large Integer (Premium) - [ ] 2387.Median of a Row-Sorted Matrix (Premium) - [ ] 302.Smallest Rectangle Enclosing Black Pixels (Premium)