Doubling the Search Range Until the Target Is Found, Explained

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

Doubling the Search Range Until the Target Is Found

Data Structures and Algorithms · Chapter 9: SearchingSection 9.4 · lesson 38 of 8710 min · free with a free account

← Splitting a Sorted Collection in Half, RecursivelyNext lesson: Stacks →

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

Exponential search doubles a bound, then binary searches the bracket.

  • Explain how exponential search doubles a bound to bracket the target
  • Implement exponential search with a capped bracket and a binary search phase
  • Search sorted data of unknown size using a sentinel past the end
  • Compare the order log i cost of galloping with the order log n cost of binary search

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,520 words). Read along, or search it.

Opening Question

A Directory of Unknown Length

You're looking for a name in a printed directory, but you don't know how many pages it has. You can't open it in the middle, because you can't say where the middle is. So you look at page one, then two, then four, then eight, doubling each time, until you land on a name that comes after yours. Now your name lies between the last two pages you looked at, and you search only that stretch. The trick helps even when you do know the size. If your name is near the front, there's no sense starting in the middle of a huge book. This is exponential search, also called galloping search.

The Problem

Two Weak Spots of Binary Search

Plain binary search has two weak spots. When the size is unknown, there's no last position, so there's no middle to probe. Think of a sorted feed read one item at a time, or a quantity that keeps growing. And when the target is near the front of a huge array, the first probe still lands in the middle. It still needs about twenty probes for a million values, even if the target sits at position three. One cure fixes both: find a small range that must hold the target, at a cost that depends on how far from the front it is. Then binary search that range.

Phase One

Doubling the Bound to Trap the Target

Phase one doubles a bound. Take the twenty even numbers from two to forty, sorted, and search for twenty-two. Position zero holds two, not the target. So set the bound to one, and while the value at the bound is smaller than the target, double it. Position one holds four: smaller. Position two holds six, position four holds ten, and position eight holds eighteen: all smaller. Position sixteen holds thirty-four. That's not smaller, so the gallop stops. Why is that enough? The previous bound, eight, held a smaller value, so the target isn't at or before it. The current bound holds a larger value, so it isn't after it. The target is trapped in a bracket, from half the bound to the bound. Here, that's positions eight to sixteen.

Phase Two

Binary Search Inside the Bracket

Phase two is an ordinary binary search inside the bracket. The middle of eight and sixteen is twelve, holding twenty-six: too big. Then position nine holds twenty: too small. Position ten holds twenty-two. Found. One read at position zero, five gallop reads, and three binary probes: nine reads in all.

Implementation

Read Helper, Gallop, and Capped Bracket

In code, a helper called read returns the value at a position, and counts each read. Past the end, it returns the largest possible int, a detail that matters soon. The method returns minus one for an empty array, and zero if position zero matches. Then the gallop: while the bound is inside the array, and the value there is too small, double it. The bracket runs from half the bound to the bound, capped at the last position, because the final doubling may overshoot the end. And binary search range is the binary search from before, limited to positions low through high.

Worked Example

Reads for Four Different Targets

Run it on the same twenty values. The target two is at position zero, and costs one read. Eight costs five reads: position zero, the bounds one, two and four, then one binary probe at position three. Thirty-six shows the cap. The bound doubles from sixteen to thirty-two, past the end, so the bracket is cut to positions sixteen through nineteen. Seven reads. And a hundred is larger than everything. The search reaches the end, and correctly reports minus one, after nine reads. If the target is smaller than everything, the bracket is just positions zero to one. And with duplicates, it returns one matching position, not necessarily the first.

Unknown Size

A Sentinel Past the End

Now remove one assumption. Suppose the program never learns how many values there are. It can read by position, but the length is never revealed. Plain binary search can't even begin. Exponential search can, because phase one never asks for the size. It only needs to learn that a probe has gone past the end. The trick is a sentinel: a read beyond the real data returns a value larger than anything that could be searched for. The read helper already does that, with the largest int. So positions past the end act like infinity. A probe that overshoots just looks too big, and ends the gallop. The top of the bracket is simply the bound, with no cap. A test hides a hundred thousand values, one, four, seven, ten, and so on, from the search, which is never told the length. The value at position forty costs thirteen reads. The one at position seventy thousand costs thirty-five. A missing value like two returns minus one. So does a value larger than everything: the first infinity ends the gallop. Two cautions. The data must really be sorted. And the sentinel must be larger than every value that might be searched for, including the target itself.

Quick Check

The Bracket for Sixteen

Quick check. Six sorted values, one, four, seven, ten, thirteen, sixteen, are hidden behind the unknown-size search. Search for sixteen. Which bracket does phase one hand to the binary search? Four to eight, two to four, or four to five? Pause, and predict. Four to eight. The gallop reads positions one, two and four, holding four, seven and thirteen: all smaller than sixteen. Position eight is past the end, so it reads as the largest int. That's not smaller, and the gallop stops. The method never knows the length, so the top isn't cut to five. Inside the bracket, position six also reads as the largest int, and the search still finds sixteen at position five.

Analysis

About Two Log i Reads

Now count the work. Let i be the target's position, counting from zero. In phase one, the bound takes the values one, two, four, eight, and stops near i. That takes about log two of i doublings. In phase two, the bracket runs from half the bound to the bound. The bound is under two i, so the bracket is shorter than i, and halving it takes about log i probes. Together, that's about two log i reads. Big O drops the two, so the cost is order log i. Plain binary search costs order log n, where n is the size of the whole array. Exponential search depends on how far the target is from the front.

Experiment

Break-Even Near the Square Root of n

Measured on a million sorted values: at position ten, the gallop uses nine reads, against eighteen for binary search. At position one hundred, it's thirteen against twenty. The two meet near position one thousand, the square root of a million. That's no accident. Two log i is smaller than log n, exactly when i is smaller than the square root of n. Beyond that, the gallop loses. At position ten thousand, it needs twenty-nine reads against seventeen, and at the very end, forty against twenty: about twice as many. But since i can never exceed n, it's never worse by more than a constant factor.

Quick Check

Break-Even for Two to the Sixteenth

One more check. A sorted array holds sixty-five thousand, five hundred thirty-six values: two to the sixteenth. Roughly where do the gallop and binary search break even? Position two fifty-six, four thousand ninety-six, or thirty-two thousand? Pause, and decide. Around position two fifty-six, the square root of n. Binary search needs about sixteen reads anywhere, since log n is sixteen. At two fifty-six, the gallop needs about two times eight: sixteen as well. At four thousand ninety-six, it needs about twenty-four, already worse, and at thirty-two thousand, about thirty.

Decision Guide

Gallop or Plain Binary Search

So which should you use? If the array is sorted, its size is known, and the target could be anywhere, use plain binary search. Galloping gains nothing there, and may cost twice as much. If the length is never given, use exponential search, since binary search can't start. And if most lookups hit the first few hundred positions, gallop too. For unsorted data, neither works: scan from the front, or sort first. And for twenty values, either is fine, so pick the simpler plain binary search.

Common Mistakes

Four Galloping Pitfalls

Watch for four mistakes. Start the bound at zero, and it never moves: zero doubled is still zero. Forget to cap the top of the bracket, and the search reads past the end of the array. Start phase two at position zero, and it stays correct, but throws the savings away. Begin at half the bound. And for arrays of more than about a billion positions, doubling an int bound can overflow. Use a long.

Key Takeaways

Exponential Search Essentials

To sum up. Exponential search doubles a bound, one, two, four, eight, until the value there reaches the target. Then it binary searches the bracket, from half the bound to the bound. It works on data of unknown size, when positions past the end read as a sentinel larger than any target. It costs order log i, which beats binary search roughly when i is below the square root of n.

Think About It

Word Suggestions from a Sorted List

Something to think about. A dictionary app suggests words as you type, from a sorted list of a million words. Most lookups start with common prefixes near the front. Would you gallop, or use plain binary search? What would you measure to decide?

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 Doubling the Search Range Until the Target Is Found

What is exponential search?
Exponential search, also called galloping search, finds a target in sorted data in two phases. First it doubles a bound, 1, 2, 4, 8, and so on, until the value at the bound is no longer smaller than the target. The target then lies between bound / 2 and the bound, and an ordinary binary search finishes inside that bracket, capped at the last position if the bound overshoots.
What is the time complexity of exponential search?
Exponential search runs in O(log i) time, where i is the target's position. Phase one takes about log2 i doublings, and the bracket it produces is shorter than i, so binary search adds about log i more probes, for about 2 log i reads in total. That beats binary search's log n when i is below roughly the square root of n, and otherwise costs at most about twice as many reads.
How do you search a sorted list of unknown size?
Use exponential search, because its doubling phase never needs the length, only a way to tell that a probe went past the end. Make reads beyond the real data return a sentinel larger than any value that might be searched for, such as Integer.MAX_VALUE when targets are always smaller. An overshooting probe then looks too big and ends the gallop, and binary search runs on the bracket.
When should you use exponential search instead of binary search?
Use exponential search when the data's length is unknown or when most targets sit near the front, such as within the first few hundred positions of a large array. If the size is known and the target could be anywhere, plain binary search is better, since galloping can take about twice as many reads near the end. On a million values, the two break even near position 1,000.

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 →