Binary Search, Explained | Data Structures and Algorithms

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

Binary Search

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

← Checking Every Element One at a Time Until the Target AppearsNext lesson: Splitting a Sorted Collection in Half, Recursively →

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

Iterative binary search on sorted arrays, its pitfalls, and variations.

  • Explain why binary search requires sorted data and constant-time index access
  • Implement iterative binary search with a correct low, mid, and high window
  • Avoid off-by-one and midpoint overflow bugs
  • Adapt binary search to find the first occurrence or the insertion point

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

Opening Question

Guessing a Number from One to a Hundred

Someone picks a whole number from one to a hundred. After each guess, they tell you only: higher, or lower. Guess one, then two, then three, and so on, and it could take a hundred guesses. Guess fifty first. Whatever the answer, half the numbers are gone at once. Keep guessing the middle of what's left, and seven guesses are always enough. Binary search plays exactly this game on a sorted array. Each comparison with the middle element throws away half of what remains.

Key Rule

Binary Search Needs Sorted Data

Binary search relies on one fact. If the middle value is smaller than the target, every value to its left is smaller too. That's only true when the data is sorted. Then one comparison throws away a whole half, with complete confidence. Now search for fifty-eight in an unsorted array. The middle is forty-two, which is smaller, so the left half is thrown away, and with it, the fifty-eight. It reports: not found. Binary search never checks that the data is sorted. Unsorted data gives wrong answers, silently. It also needs every element reachable by index in constant time. That rules out a linked list, where reaching the middle means walking from the head.

Definition

The Low, Mid, and High Window

The search keeps a window of positions that could still hold the target, using three index variables. Low is the first position still in play. High is the last. And mid is the middle of the window, where the next comparison happens. At the start, the window is the whole array: low is zero, and high is the length minus one. Each pass compares the middle element with the target. If they're equal, return mid. If the middle is smaller, the target can only be to the right, so low becomes mid plus one. If it's larger, the target can only be to the left, so high becomes mid minus one. The loop runs while low is at most high. When low passes high, the window is empty, and the method returns minus one.

Implementation

The Method and Its Invariant

Here's the whole method. Mid is computed as low plus half the distance to high, for a reason you'll see shortly. The loop keeps one promise true on every pass: if the target is in the array, it's somewhere between low and high. Each branch shrinks the window without breaking that promise. A promise like this is called a loop invariant, and it's what makes the method correct.

Trace

Finding Fifty-Eight in Four Steps

Trace a search for fifty-eight in this sorted array of fifteen values. Step one: low is zero, high is fourteen, so mid is seven, holding forty-two. That's smaller, so low becomes eight. Step two: mid is eleven, holding sixty-four. That's larger, so high becomes ten. Step three: mid is nine, holding fifty-three. Smaller, so low becomes ten. Step four: low, mid and high are all ten, and that cell holds fifty-eight. Found. Fifteen elements, and four comparisons. Checking one by one would have taken eleven.

Quick Check

Last Comparison Before Giving Up

Quick check, on the same array. Now search for fifty, which isn't there. Which value is the last one it compares with, before it gives up? Forty-seven, fifty-three, or fifty-eight? Pause, and predict. Forty-seven. The first two steps match the last search: forty-two sends it right, and sixty-four sends it left, so high is ten. Mid nine holds fifty-three, which is larger, so high becomes eight. Now low, mid and high are all eight, holding forty-seven, which is smaller, so low becomes nine. Low has passed high. The window is empty, and it returns minus one. That last step is why the loop runs while low is at most high. With one element left, that element still has to be checked.

Common Mistakes

Three Off-by-One Bugs

Binary search is easy to describe, and easy to get slightly wrong. Three small changes each break it. Write the loop as low less than high, and it stops with one element left, unchecked. Search a one-element array for its only value, and it returns minus one. Write high equals mid, instead of mid minus one, and mid stays in the window. The window can stop shrinking, and the loop never ends. Searching that array for fifty did exactly that, while eighty-five still worked. And start high at the array's length, and mid can land one past the end. The fixes are all small: less than or equal, mid plus one, mid minus one, and the length minus one.

Common Mistake

Integer Overflow in the Midpoint

One more trap hides in the middle calculation. Low plus high, over two, appears in many textbooks, and works for small arrays. But low plus high is computed as an int before it's divided. If both are large, the sum passes the largest int, about two point one billion, and wraps around to a negative number. With one and a half billion and two billion, it prints minus three hundred ninety-seven million. The safe form, low plus half the distance to high, prints one point seven five billion. Subtracting first never produces a number bigger than high, so it can't overflow. Arrays that large are rare, but a method that's right only for small inputs is a bug waiting for its moment.

Analysis

Halving a Thousand Down to Nothing

Why is it so fast? Each comparison removes at least half the window. Start with a thousand elements. After one comparison, five hundred remain. Then two fifty, one twenty-five, sixty-two, thirty-one, fifteen, seven, three, and one. After ten comparisons, nothing is left. In general, the most comparisons binary search ever needs is the floor of log base two of n, plus one. Running it on every possible target confirms it: three for seven elements, ten for a thousand, and twenty for a million. Doubling the array adds only one comparison, so a billion elements need at most thirty. The best case is a single comparison, and the loop needs only constant extra memory. Those counts don't include sorting the data in the first place.

Variations

First Occurrence and Insertion Point

A plain binary search stops at the first match it happens to find. With duplicates, that could be any of them. In ten, twenty, twenty, twenty, thirty, forty, the plain search for twenty lands on position two, the middle copy. To find the first copy, don't stop on a match. Remember it, set high to mid minus one, and keep searching left. That returns position one. Sometimes the value is missing, and the question is where it belongs. The insertion point is the index of the first element that's not smaller than the target. It uses a different window. High starts at the length, one past the last candidate. The loop runs while low is less than high, and a middle that's not smaller than the target sets high to mid. For twenty-five, it returns four. The two styles must never be mixed: the loop condition and the updates have to belong to the same convention.

Java API

How Arrays.binarySearch Reports a Miss

Java's own Arrays dot binary search uses the insertion point to report a miss. It returns minus the insertion point, minus one. So a negative result still tells you where the value belongs. On the same array, it returns minus five for twenty-five, and for twenty it may return any matching position.

Quick Check

Searching for Thirty-Five

Quick check. The array holds ten, twenty, thirty, forty. What does Arrays dot binary search return for thirty-five: minus four, minus five, or three? Pause, and decide. It returns minus four. Thirty-five belongs at position three, in front of forty, so the insertion point is three. Minus three, minus one, is minus four. Three would mean thirty-five was found there, and minus five would put it after forty.

Key Takeaways

Binary Search Essentials

To sum up. Binary search needs sorted data, and constant-time access by index. Each comparison with the middle throws away half the window. Use low at most high, mid plus one and mid minus one, and compute mid as low plus half the distance. It needs at most floor of log n, plus one comparisons. And small changes to the match rule give the first occurrence, or the insertion point.

Think About It

Counting Copies of a Value

Something to think about. How would you change the first-occurrence search, to find the last occurrence instead? Then use both versions to count the copies of a value, without scanning the whole array.

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 Binary Search

How does binary search work?
Binary search finds a target in a sorted array by comparing it with the middle element of a window and discarding the half that cannot contain it. The window starts at low = 0 and high = a.length - 1. If a[mid] is smaller than the target, low becomes mid + 1; if larger, high becomes mid - 1. The loop runs while low <= high and returns -1 once the window is empty.
Why is mid = low + (high - low) / 2 used in binary search?
Writing mid = low + (high - low) / 2 avoids integer overflow. The common form (low + high) / 2 adds two ints first, and if both are large the sum passes Integer.MAX_VALUE, about 2.1 billion, and wraps to a negative number. With low = 1,500,000,000 and high = 2,000,000,000, it gives -397,483,648. Subtracting first never produces a value larger than high.
What is the time complexity of binary search?
Binary search runs in O(log n) time, because each comparison removes at least half of the remaining window. It needs at most floor(log2 n) + 1 comparisons: 10 for a thousand elements, 20 for a million, and at most 30 for a billion. Doubling the array adds only one comparison. The best case is a single comparison, and the iterative version uses constant extra memory.
What does Arrays.binarySearch return when the value is not found?
When the key is missing, Arrays.binarySearch returns -(insertion point) - 1, where the insertion point is the index of the first element greater than the key. For the sorted array {10, 20, 30, 40} and key 35, the insertion point is 3, so it returns -4. A negative result therefore still tells you where the value belongs. With duplicates, a found key may return any matching position.

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 →