Splitting a Sorted Collection in Half, Recursively, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 9.3 Free with a free account

Splitting a Sorted Collection in Half, Recursively

Data Structures and Algorithms · Chapter 9: SearchingSection 9.3 · lesson 37 of 879 min · free with a free account

← Binary SearchNext lesson: Doubling the Search Range Until the Target Is Found →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Recursive binary search with low and high, its stack depth, and recurrence.

  • Implement recursive binary search with two base cases and two recursive cases
  • Trace the chain of calls for present and absent targets
  • Explain why recursive binary search needs only about log n stack frames
  • Solve the recurrence T(n) = T(n/2) + c to show logarithmic cost

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,351 words). Read along, or search it.

Opening Question

How Many Frames for a Billion Values

After one middle test, what's left of a binary search? The same search, on half the range. A method that calls itself is a natural way to say that. But every call takes a frame on the stack. So how many frames would it need, to search a billion sorted values? Hold that question.

Key Idea

Two Base Cases, Two Recursive Cases

Searching from index low to index high, both included, comes down to four situations. If the range is empty, low is past high, so return minus one. If the middle element is the target, return its index. Those are the base cases. If the middle is smaller than the target, search the right part, mid plus one to high. If it's larger, search the left part, low to mid minus one.

Implementation

A Public Wrapper and a Recursive Search

Here's the method. A short public binary search hides two extra parameters, and starts with the whole array, from zero to the length minus one. Search checks for an empty range first. Then it computes mid safely, as low plus half the distance to high. Notice return search, in both recursive cases. A call has nothing left to do, except hand back what the deeper call found. Run it: fifty-six is at index eight, forty-two at seven, and sixty isn't there.

Parameters

Only Low and High Change

The array and the target are passed along unchanged. The array is never copied: each call just receives a reference to it. Only low and high change. Going right, low becomes mid plus one. Going left, high becomes mid minus one. Each call gets its own pair, in its own stack frame.

Trace

Four Calls to Find Fifty-Six

To watch it work, this version numbers each call, indents it by depth, and prints its range, and what it returns. Search for fifty-six. Call one sees forty-two at mid seven, so it goes right. Call two sees a hundred five, and goes left. Call three sees seventy-two, and goes left. Call four finds fifty-six at index eight. Then the answer travels back: call four returns eight to call three, which returns it to two, then one. Each call starts the next, and waits for it. The range shrinks, but the array itself is never copied.

Trace

An Empty Range for Sixty

Now sixty, which isn't there. The first four calls are the same, because sixty is also larger than fifty-six. So call four goes right, and call five receives low nine, and high eight. The range is empty, and minus one travels back up. Five calls: four tests, plus the empty range.

Key Idea

A Chain of Calls, Not a Tree

Forty-two, the very first middle, takes a single call. Every other target takes a chain of calls, one inside another. Each call makes at most one further call. So the calls form a straight chain, not a branching tree, and that keeps the cost small. A method that calls itself twice per level branches instead, and its calls multiply.

Quick Check

Dropping the Return Keyword

Quick check. This version drops the word return, in front of both recursive calls. It still compiles. It searches the same fifteen values, for fifty-six. What does it print? Pause, and predict. It prints -1. The deeper calls do find fifty-six, at index eight, but each answer is thrown away. It compiles because the method still ends with return minus one, and that's what the top call reaches. Only a target at the very first middle is found. Forty-two still returns seven, but a hundred five returns minus one.

Common Mistake

Copying Halves Costs Linear Work

Another tempting version passes copies of the halves, made with Arrays dot copy of range, instead of low and high. The answers are right, but count the copying. On a million values, one search for a missing target copies 999,989 elements. That's about one whole copy of the array, so the work is back in proportion to n. Passing two integers costs almost nothing.

Common Mistake

Recursing on Mid Never Shrinks

A third bug: recursing on mid, instead of mid plus one. On one, two, searching for five, mid is zero, and the next call gets the same range again. The range never shrinks, so the calls never stop, until Java gives up with a stack overflow error. Every recursive case must hand on a strictly smaller range, or the calls never end.

Comparison

Recursive Versus Looping Binary Search

The halving loop and the self-calling method do the same work. The recursive one mirrors the definition: search the smaller range. The loop keeps two moving boundaries in your head, but its extra memory is just a few variables. The recursion needs one frame per call. Their typical bugs differ: a dropped return here, a wrong boundary update there. On fifty thousand random sorted arrays, the two versions always agreed. In timing tests, the recursive one is usually a few percent slower. Choose by clarity, and by how much stack you can afford.

Stack Depth

About Thirty Frames for a Billion

Back to the opening question. Each waiting call holds a frame, so the deepest moment is the longest chain of calls. This program counts the calls for every present target, and for every gap between them, and keeps the largest. Fifteen values need at most four frames, or five when the target is absent: the extra one is the final, empty range. A thousand needs ten, and a million needs twenty. A billion would need about thirty. That's nothing.

Contrast

Recursive Linear Search Overflows

Compare a recursion that shrinks the problem by just one. This linear search checks one element, then searches the rest. On two hundred thousand elements, Java stops with a stack overflow error. It needs one frame per element. Its last action is the self-call, a tail call. Some languages reuse the frame for that, but Java doesn't, so it still overflows. Binary search is safe only because its depth is about log n.

Analysis

Unrolling the Halving Recurrence

One call computes mid, and compares: a constant amount of work, c. Let T of n be the work to search n elements. Then the call searches at most half the range: T of n over two. And a single element costs c. So T of n equals T of n over two, plus c. That's a recurrence: a cost stated in terms of a smaller one. Unroll it. T of n over two is itself T of n over four, plus c. So the total is T of n over four, plus two c. After k levels, it's T of n over two to the k, plus k times c. The size reaches one when k is log base two of n. So T of n is c times, log two of n, plus one. That's logarithmic.

Experiment

Each Doubling Adds One Call

Does it match reality? Run the counter on a thousand, two thousand, and four thousand values. Ten, eleven, twelve: each doubling of n adds exactly one call. That's the signature of a logarithmic cost. Compare a recursion that removes one element per call. T of n equals T of one less than n, plus c. That unrolls to c times n: a million calls, where halving needs twenty.

Quick Check

Calls for Eight Thousand Values

Quick check. Run the same counter on eight thousand values, with every target present. What's the largest number of calls it reports? Pause, and predict. At most thirteen. Eight thousand is twice four thousand, and doubling adds one call, so twelve becomes thirteen. Check it with the formula: log base two of eight thousand is just under thirteen. Round down to twelve, and add one. Twenty-four would be doubling the count, and fourteen is the count when the target is absent.

Common Mistakes

Recursive Binary Search Pitfalls

The usual mistakes. Writing search, instead of return search: it compiles, and returns minus one for almost every target. Passing copied halves, which costs about n. Recursing on mid, so the range never shrinks. And searching unsorted data, which gives wrong answers. Finally, assuming every recursion is safe because this one is. Shrinking by one needs n frames, and Java doesn't remove tail calls.

Key Takeaways

Recursive Binary Search Essentials

To sum up. Binary search is naturally recursive: what's left is the same search on a smaller range, passed as low and high. Two base cases, two recursive cases. Pass indices, never copies, and always return the deeper result. The calls form a chain, about log n deep, so the stack stays tiny. And T of n equals T of n over two, plus c, which unrolls to c log n: doubling n adds one call.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Splitting a Sorted Collection in Half, Recursively

How do you write binary search recursively in Java?
Pass the array, the target, and the range bounds low and high, and return -1 when low > high. Otherwise compute mid = low + (high - low) / 2, return mid if a[mid] equals the target, return search(a, target, mid + 1, high) if a[mid] is smaller, and return search(a, target, low, mid - 1) if it is larger. A public wrapper starts the search at 0 and a.length - 1.
Why does recursive binary search return -1 when the target is in the array?
A common cause is calling search without return in front of the recursive calls. The deeper call finds the index, but the result is thrown away, and the top call falls through to its final return -1. The code still compiles, and only a target at the very first middle is found. Writing return search(...) in both recursive cases hands the answer back up the chain.
How deep does recursive binary search go on the call stack?
Recursive binary search makes a chain of about log2 n nested calls, so its stack stays tiny: about 10 frames for a thousand values, 20 for a million, and about 30 for a billion, plus one when the target is absent. By contrast, a recursive linear search needs one frame per element and overflows the stack on large arrays, since Java does not eliminate tail calls.
What is the recurrence relation for binary search?
The recurrence is T(n) = T(n/2) + c: one call does constant work, then searches at most half the range. Unrolling gives T(n/2^k) + kc, and the size reaches 1 when k = log2 n, so T(n) = c(log2 n + 1), which is O(log n). Each doubling of n adds exactly one call, while a recursion that removes one element per call costs c times n.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →