WhiteBox
DSA
Start coding DSA Beyond LeetCode System Design AI Engineering White Room
RoadmapProblem sets
Quizzes Dan Ladder Contests Templates Graph Editor
Guides Library
Login Sign up
Sign up Log in

Workspaces

Start coding DSA Beyond LeetCode System Design AI Engineering White Room

DSA

Overview Roadmap Problem sets Quizzes Dan Ladder Contests Templates Graph Editor CP Guessr

Library

Library Guides

Community

Leaderboard Contributors Refer & Earn Cosmetics

Tools

Resume Reviewer Job Boards Changelog

Arrays and searching 0/120

DSA 0 of 360 problems solved
0%
Overview

Curriculum

    1. Hashing 0/11
    2. Two pointers 0/12
    3. Sliding window 0/21
    4. Prefix sums 0/29
    5. Binary search 0/20
      1. Binary search technique
      2. Sorted arrays 0/10
      3. Search on the answer 0/10
    6. Heaps 0/11
    7. Greedy and intervals 0/9
    8. Linked lists 0/8
    9. Data structure design
  1. DSA
  2. / Arrays and searching

Binary search · 2 of 3

Sorted arrays

Use the library's lower and upper bound for membership, counts and runs of equal values, then halve a rotated array and an array with peaks, which are not sorted.

2,752 words · 13 min read

Lesson Problems10 Reading4

Books1

  • Competitive Programmer’s Handbook, Section 3.3: Binary search Pages 31 to 34: the halving loop, a version that jumps by shrinking steps, the C++ lower_bound family, and the smallest value for which a condition holds. (opens in a new tab)

Links2

  • docs.python.org bisect: Array bisection algorithm bisect_left, bisect_right and their key argument, with recipes for lookups such as the leftmost value equal to x. docs.python.org (opens in a new tab)
  • en.cppreference.com std::lower_bound What lower_bound requires of the range, what it returns, and links to upper_bound and equal_range. en.cppreference.com (opens in a new tab)

More links1

  • Errichto - Binary Search Tutorial (C++ and Python)youtube.com (opens in a new tab)
Lesson: Sorted arrays
Overview Roadmap Problem sets Log in