Paperis.

© 2026 네오쿤스. All rights reserved.

공지사항이용약관개인정보처리방침환불 정책콘텐츠·제거 요청

상호: 네오쿤스 · 대표자: 김근태 · 사업자등록번호: 751-04-03501 [사업자정보 확인] · 통신판매업 신고: 제 2026-서울서초-3586호 (서초구청)

주소: 서울특별시 서초구 서초대로 266, B103-S36호(서초동) · Tel: 010-7254-2475 · 이메일: support@paperis.app · 고객센터 운영 시간: 평일 10:00–16:00 (한국 시간, 주말·공휴일 제외) · 호스팅 서비스 제공자: Vercel Inc.

Paperis.
Algorithms — Calling Numbers One by One, Questions That Erase Half

Paperis Articles

Algorithms — Calling Numbers One by One, Questions That Erase Half

An algorithm is a sequence of steps, set out in advance and bound to end, for solving a problem. The same problem can be solved in several ways, and a way's speed is measured by how much the work grows as the input grows. It has been proven that no algorithm can always correctly tell whether any program will stop.

🌱Primer✦AI-generatedComputer Science & AI · Nov 11, 2026

Your field's papers, as audio

Pick your fields and journals — Paperis summarizes the key papers and turns them into audio. Listen on your commute.

Start Paperis free →

Algorithms — Calling Numbers One by One, Questions That Erase Half

A Number Between 1 and 100

One person keeps a single number between 1 and 100 in their mind. Another person must guess that number, and the person who chose it answers only with "Correct", "Larger", or "Smaller".

The first person guesses sequentially starting from 1. "1?" "Larger." "2?" "Larger." If the chosen number is small, it ends quickly, but if the chosen number is 100, they have to call out one hundred times.

The second person calls out 50 first. If the answer "Larger" comes back, there is no need to look at 1 through 50 again. Now they call out 75, which is the exact middle of the remaining 51 to 100, and erase half again depending on the answer. With each single question, the remaining candidates are cut in half (OpenStax Introduction Computer Science 3.3). If you divide 100 in half seven times, it becomes smaller than 1, so if you calculate it, you can guess the chosen number within seven times no matter what it is.

Both people eventually guess the number. The only difference is how many times they ask, and that difference widens dramatically as the range gets broader. This article takes this single game and follows how it explains what an algorithm is, why there are multiple ways to solve the same problem and why their speeds differ so much, and why there are problems that a computer cannot solve no matter how fast it is.

An Algorithm Is a Finite Sequence of Steps

The method the two people followed can be written down in words. The first person's method is "Call out starting from 1, and go up one by one until you hit the right answer." The second person's method is "Call out the middle number of the remaining range, and erase half based on the answer." An algorithm is a finite sequence of steps set down to solve a problem (OpenStax Introduction Computer Science 1.1) (OpenStax Introduction Computer Science 3.1).

An algorithm starts by receiving something and ends by putting something out. An input is the material the algorithm receives to begin, and an output is the result the algorithm puts out at the end. In number guessing, the input is the range of 1 to 100 and the answer returned for each question, and the output is the single guessed number. Computer science typically frames problems in this form, where it is decided which output matches which input (OpenStax Introduction Computer Science 3.2).

To leave this sequence to a computer, two things must be observed. One is that the steps must not be ambiguous. Between humans, "Call out somewhere around the middle" is enough. When there are fifty remaining numbers from 51 to 100 and thus two middles, people figure out for themselves which one to call. A computer walks through the written steps right there on the spot without adding or subtracting anything (OpenStax Introduction Computer Science 3.1). Therefore, what to do at every fork in the road must be settled as a single action, such as "If there are two middles, call out the smaller one."

The other is that it must have an end. The second method stops without fail when the remaining range shrinks to a single space. If a stopping condition is missing from a method that repeats the same steps, that method repeats the same task endlessly (OpenStax Introduction Computer Science 2.1).

A program is these steps translated into a language that a computer reads. A program is a bundle of commands that write down what a computer is to do in order. If an algorithm is the method, a program is that method translated into a specific programming language to make it actually run (OpenStax Introduction Computer Science 3.1). The task of translation is covered by another piece in this series, "Programs and Programming Languages — A Score Written by People, a Piano That Plays Only the Holes". The two methods of the game were already algorithms the moment they were written on paper, and the computer is a machine that follows them precisely as written.

Big Questions Into Small Questions of the Same Shape

The fact that the second person called out 50 first involves two mental habits. Computational thinking is a way of thinking that breaks a complex problem down into smaller parts and refines the solution so it can be written as steps that a human or a computer can follow (OpenStax Introduction Computer Science 2.1). There is not yet a single definition of this that everyone agrees on (DOI: 10.1177/21582440211016418).

Decomposition is the work of dividing a complex problem into smaller parts that are easy to handle (OpenStax Introduction Computer Science 2.1). The question "where is it between 1 and 100?" turns into "is it in the front half or the back half?". When you hear the answer, the same question remains with only a smaller size: "where is it between 51 and 100?". Reducing a big problem into smaller problems of the same shape until they are small enough to answer right away is one of the representative frameworks for designing algorithms (OpenStax Introduction Computer Science 3.4).

Abstraction is the work of leaving behind only what is needed for the task at hand and stripping away or hiding irrelevant details (OpenStax Introduction Computer Science 2.1). Whether the hidden thing is a number or a person's name, the second method needs only one piece of information. It is enough to be able to compare what is being searched for and what was called out, and say which side comes first. Even when comparing names, a computer compares the numbers assigned to each letter in order (OpenStax Introduction Computer Science 3.1). The work of turning letters into numbers is covered in another part of this series, "Bits and Data — Raised Dots and Flat Spots, a Code the Fingertips Know".

You do not need a computer or code for this kind of thinking. There are methods of teaching computational thinking through activities done with movement or paper without a computer, and studies so far report good results, but confirming this at a large scale still remains to be done (DOI: 10.4018/978-1-7998-4576-8.ch009). Even so, teacher training programs repeatedly report the misunderstanding that computational thinking is the same thing as coding. This point was compiled by a review paper synthesizing 54 pieces of literature, and is a preprint before peer review (DOI: 10.20944/preprints202602.1017.v1). A review examining 80 studies on computational thinking education also concluded that education in this field leans heavily toward code (DOI: 10.1177/21582440211016418). The starting point of an algorithm is the thought of splitting and distilling a problem, and code comes afterward.

Calling One by One and Erasing by Halves

Now we give names to the two methods. Sequential search is a method of finding things by checking collected items one by one in order from the beginning (OpenStax Introduction Computer Science 3.5). Binary search is a method of finding things by comparing what you are looking for with the exact middle of an ordered list, erasing half of the remaining candidates all at once (OpenStax Introduction Computer Science 3.5). The former is the first person's method, and the latter is the second person's method.

The reason erasing by halves works is that the single word "Larger" tells you which half can be safely erased. The numbers from 1 to 100 are lined up in order of size from the beginning, so just the answer that it is larger than 50 drops the entire front half. Let us suppose that the same 100 numbers are randomly mixed and lined up in a single row. Even if the number in the middle slot of the row is smaller than the number you are looking for, you cannot know whether the number you are looking for is before or after that slot. Therefore, search by erasing halves can only be used when the list is already arranged in order in advance (OpenStax Introduction Computer Science 3.5). Search that checks one by one can be used even when there is no order (OpenStax Introduction Computer Science 3.5).

The same bars in two lines. In the line ordered by size, the single answer "Larger" than the middle slot drops the entire front half. In the shuffled line, the same answer cannot tell whether the number is before or after that slot. Search by erasing halves works only on a list already in order.

Arranging in order beforehand also has a name. Sorting is the task of rearranging scattered items in a predetermined order, such as from smallest to largest (OpenStax Introduction Computer Science 3.5). Because someone must sort first for search by erasing halves to work, sorting serves as the foundation for many other algorithms (OpenStax Introduction Computer Science 3.5). The task of sorting is not free either, so the more items there are to line up, the more work increases (OpenStax Introduction Computer Science 3.5). Several methods of sorting are known, but the single best one cannot be chosen for every case. The appropriate method varies depending on how much data there is, how tidy it already is, and how much spare room there is to use separately while working (DOI: 10.28925/2663-4023.2023.21.8698).

Search by erasing halves has one more condition. You must be able to leap straight to the middle slot. This condition depends on how the data is stored. A data structure is an arrangement that determines what shape data is lined up in and how it is retrieved and used (OpenStax Introduction Computer Science 3.1). Binary search is fast in a list where every slot is numbered so that any arbitrary slot can be opened immediately. In a list where you can only reach slots by following them consecutively from the front slot to the next, it takes a long time just to reach the middle, making binary search slow (OpenStax Introduction Computer Science 3.5). Whether an algorithm can even be written often depends on how the data is represented (OpenStax Introduction Computer Science 3.1). Search by erasing halves assumes these two prerequisites: a sorted list and slots that can be leaped to directly.

When the Range Doubles

This time, we play again with the range expanded from 1 to 200. If the chosen number is 200, the person calling them out one by one must call out two hundred times. Because the range doubled, the number of questions also doubled. The person who deletes half reduces the remaining range to a hundred slots or fewer with a single "100?", and from there solves it exactly the same as the first game. The increased question is only one. When a list grows twice as long, searching by checking one by one increases the steps in the worst case by double, whereas searching by deleting half increases by only one step even in the worst case (OpenStax Introduction Computer Science 3.3). Even if the range is continually expanded to 400 and 800, the first person's questions double every time, while the second person's questions add only one each time.

Worst-case questions as the guessing range doubles from 1–100 to 200, 400 and 800. Calling one by one takes one hundred, then two hundred, doubling each time; erasing by halves takes seven, adding only one each time.

When comparing the two people, what we counted was the number of questions. We did not consider who speaks faster. We count the number of steps for the same reason when comparing algorithms. Because running the same method on a fast computer finishes quickly and running it on a slow computer takes a long time, it is better to count the steps taken to see the difference in the method itself (OpenStax Introduction Computer Science 3.3). Time complexity represents how much the number of steps an algorithm must take increases as the size of the input grows (OpenStax Introduction Computer Science 3.3). The two methods of number guessing split right at this shape of increase.

There is also a short label attached to that shape. Big O notation is a method of writing down in a simple symbol what shape the number of steps grows into when the input becomes very large (OpenStax Introduction Computer Science 3.3). The difference between the two people—"increases in proportion to the range" and "increases by one each time the range doubles"—is written in this notation as a single symbol each. This article writes it in words instead of symbols.

Then, is any fast method good? There is one more thing to ask the two people. It is whether the number held in hand when it finishes is truly the chosen number. Correctness is the property where an algorithm produces the expected output for all possible inputs (OpenStax Introduction Computer Science 3.2). Both methods definitely finish and the number guessed at the end is the correct answer, so both are right. What split is only the number of questions. Conversely, there are also programs that produce the correct answer while taking unnecessarily long (OpenStax Introduction Computer Science 3.3). Showing that something is correct is also not always easy. Number guessing can try everything because there are only a hundred numbers that can be chosen, but an algorithm that can receive endlessly many inputs has no way to plug them all in one by one (OpenStax Introduction Computer Science 3.2). Whether it produces the correct answer and how fast it produces it are separate questions.

Things That Cannot Be Done by Trying Every Combination, Things That Simply Cannot Be Done

What if nobody had been erasing half the options? The person calling them out one by one would have gotten it right eventually, too. When the number of candidates is fixed, the method of calling out every single one will reach the answer eventually (OpenStax Introduction Computer Science 3.2). The remaining question is when it will get there. When comparing algorithms, what matters just as much is the time it takes and the space it occupies (OpenStax Introduction Computer Science 3.2).

The situation changes if the hidden thing is not a single number, but a combination woven from multiple pieces. As the pieces increase, the candidate combinations to test explode, so the method of trying every candidate is only useful when there are very few pieces. Even if computers get faster, this limit remains (OpenStax Introduction Computer Science 3.4). If it is a method where every single additional input doubles the work, just a thousand items to process are enough to make it take longer than the age of the universe (OpenStax Introduction Computer Science 3.3). This is a limit of the trial-and-error method, and it is a separate story from whether the same problem can be solved faster using a different approach.

There are separate problems that cannot be solved by any method, no matter how much time you are given. Both ways of playing the game eventually end. So could we also build an algorithm that takes any arbitrary program and its input, and always correctly determines whether that program will eventually halt on that input? This question is called the halting problem, and it has been proven that no such algorithm that always answers correctly for every program exists. The basis for this part is an overview from a non-peer-reviewed preprint (DOI: 10.20944/preprints202512.0580.v1). An undecidable problem is a problem for which there can be no algorithm in principle that correctly answers yes or no for every input. The halting problem is a prime example of this (DOI: 10.20944/preprints202512.0580.v1).

In 1936, Alan Turing created a mathematical model of computation, what we call a Turing machine today. He intended to use this model to refute a core part of mathematician David Hilbert's project to treat mathematics through mechanical procedures. This model later became the framework that defines the scope of what computers can do (DOI: 10.1093/oso/9780198747826.003.0049). In the same 1930s, Kurt Gödel and Alonzo Church were also at the center of examining the meaning and limits of computation (DOI: 10.1093/oso/9780198747826.003.0014). The proof that the halting problem cannot be solved is commonly credited to Turing's 1936 paper. A 2026 paper examining this attribution concluded that it is difficult to state so bluntly (DOI: 10.1093/logcom/exaf075).

Black-and-white photo of teenage Alan Turing in a school jacket, facing the camera

Alan Turing at about sixteen · passport photo (possibly by Arthur Reginald Chaffin), 1928–29 · Wikimedia Commons (public domain)

There are problems where the work grows so much that even a fast computer cannot handle them if you try every candidate, and there are problems, like the halting problem, that are proven impossible to solve by any algorithm (OpenStax Introduction Computer Science 3.4) (DOI: 10.20944/preprints202512.0580.v1).

"Algorithms" in the News

The algorithm in the sentence "An algorithm recommended this video" is the same thing as the algorithm in this article. The input is data to gauge what is worth watching, and the output is a list of recommendations. The procedure itself was designed by humans (OpenStax Introduction Computer Science 3.2).

So how do we check whether a recommendation algorithm is right? If it were about guessing a number, you would just compare the target number with the guessed number and you are done. Recommendations do not have a single correct answer to compare against in that way, and there is the problem that people cannot even agree among themselves on what makes an output correct (OpenStax Introduction Computer Science 3.2).

Because the person designing the algorithm cannot handle reality in its entirety, they decide which details to keep and which to discard, creating a framework for the computer to process. This framework is called a model (OpenStax Introduction Computer Science 3.2). Saying that an algorithm is right usually means it follows that model well, and there is no guarantee that it gets right the aspects of reality that the model missed (OpenStax Introduction Computer Science 3.2). The relationship between algorithms and the social outcomes they produce is still a subject of debate today (OpenStax Introduction Computer Science 3.2).

The "algorithm" in the news also takes an input and produces an output according to preset procedures, and that result contains how the designer built the model to keep certain things and discard others. Calculations that have a computer learn from examples instead of humans writing down rules one by one are covered in "AI Models — A Calculation That Learns From Examples Instead of Rules".

Facing Number Guessing Again

Let us return to the first two people. The two people solved the same problem with different algorithms. Both came to an end and were correct, but as the range grew wider, the number of questions widened greatly. The speed of half-deletion came from the fact that the range is laid out in order of size. And it has been proven that a method to correctly judge in all cases whether any given program halts on a given input cannot be made in principle. This basis is a pre-peer-review preprint (DOI: 10.20944/preprints202512.0580.v1).

The game is a useful picture, but it differs from reality in two places. First, in the game, a human answers and thinks. Inside a computer, even comparing two values is just a single step the machine takes (OpenStax Introduction Computer Science 3.3), and the computer merely follows that step exactly as written (OpenStax Introduction Computer Science 3.1). The part that actually processes those steps one by one is covered in another piece of this series, "CPU and Memory — A Desk That Gets Cleared, Library Stacks That Stay". Second, the 1 to 100 in the game naturally has an order of size. Real data must be sorted in advance by someone and stored in a shape that allows jumping straight to the middle for half-deletion to work (OpenStax Introduction Computer Science 3.5).

Where to Look Next

  • The way computers learn from examples instead of humans writing down the rules: "AI Models — A Calculation That Learns From Examples Instead of Rules"
  • How that learning is actually the process of tweaking numbers slightly: "Neural Networks and Parameters — What It Means to Nudge Hundreds of Billions of Dials"
  • Hiding text is also a branch of algorithms (OpenStax Introduction Computer Science 3.2). Among them, public-key cryptography: "Keys and Locks — Why a Public Key Is Safe to Publish"
  • Other parts of this series: translating algorithms into programming languages is covered by "Programs and Programming Languages — A Score Written by People, a Piano That Plays Only the Holes", components that actually process the steps by "CPU and Memory — A Desk That Gets Cleared, Library Stacks That Stay", and turning text and figures into numbers by "Bits and Data — Raised Dots and Flat Spots, a Code the Fingertips Know".

Source Papers

  • "Introduction to Computer Science — 1.1 Computer Science" (2024) — OpenStax Introduction Computer Science 1.1 — Algorithms calculate using inputs and a finite number of steps to produce outputs (basis for the public definition of "having an end", description in the context of arithmetic operations).
  • "Introduction to Computer Science — 2.1 Computational Thinking" (2024) — OpenStax Introduction Computer Science 2.1 — Computational thinking is the process of breaking complex problems into smaller parts and establishing systematic solutions. Definitions of decomposition and abstraction; repetition must have a stopping condition to avoid infinite loops.
  • "Introduction to Computer Science — 3.1 Introduction to Data Structures and Algorithms" (2024) — OpenStax Introduction Computer Science 3.1 — Algorithms are precise sequences of commands for handling data, computers execute only the prescribed commands exactly as written, and programs are algorithms implemented in a programming language. Algorithm design depends on how data is represented.
  • "Introduction to Computer Science — 3.2 Algorithm Design and Discovery" (2024) — OpenStax Introduction Computer Science 3.2 — For problems where outputs correspond to inputs, finite inputs can always be solved by brute-force search, so the goal is efficient solutions. Models discard some details, accuracy means matching the expected output for all inputs, and it mainly refers to alignment with the model. Recommendations and the social consequences of algorithms are under debate.
  • "Introduction to Computer Science — 3.3 Formal Properties of Algorithms" (2024) — OpenStax Introduction Computer Science 3.3 — Execution time varies by computer, so it is measured in the number of steps. Time complexity and Big O notation. When input doubles, the worst case for sequential search doubles, while binary search increases by one unit. Exponential-time algorithms exceed the age of the universe for a thousand elements.
  • "Introduction to Computer Science — 3.4 Algorithmic Paradigms" (2024) — OpenStax Introduction Computer Science 3.4 — Divide and conquer solves problems by dividing them into smaller problems of the same form. Brute-force assignment for combinatorial problems leads to combinatorial explosion, making them usable only for very small inputs even as computers get faster.
  • "Introduction to Computer Science — 3.5 Sample Algorithms by Problem" (2024) — OpenStax Introduction Computer Science 3.5 — Sequential search works on any collection, while binary search relies on sorted lists accessible directly by index to eliminate half at a time. Sorting is the foundation for many algorithms, including binary search.
  • "Teaching Computational Thinking Unplugged" (2020) — DOI: 10.4018/978-1-7998-4576-8.ch009 — A chapter on "unplugged" computational thinking education taught without computers, noting that existing research is positive but large-scale evaluation is still needed.
  • "Generative AI to Foster Computational Thinking in Initial Teacher Education: A Thematic Literature Review and Model" (2026) — DOI: 10.20944/preprints202602.1017.v1 — A review of 54 papers (preprint). In teacher training programs, the misconception that equates computational thinking with coding is consistently reported.
  • "The Code-Centric Nature of Computational Thinking Education: A Review of Trends and Issues in Computational Thinking Education Research" (2021) — DOI: 10.1177/21582440211016418 — A review of 80 papers on computational thinking education research. Concludes that the research community lacks an agreed-upon conceptual definition and that education is code-centric.
  • "A PERFORMANCE COMPARISON OF SORTING ALGORITHMS IN DIFFERENT PROGRAMMING LANGUAGES" (2023) — DOI: 10.28925/2663-4023.2023.21.8698 — Compares nine sorting algorithms across four languages. No single one is best in all cases; performance depends on data size, structure, degree of order, and additional memory.
  • "Analyzing the Halting Problem: Limits of Computation and Decidability in Turing Machines" (2025) — DOI: 10.20944/preprints202512.0580.v1 — A preprint providing an overview of the halting problem. The problem of determining whether an arbitrary program and input will halt is undecidable (there is no algorithm that always predicts correctly for all programs).
  • "Decidability and the Entscheidungsproblem" (2017) — DOI: 10.1093/oso/9780198747826.003.0049 — Turing created a mathematical model of computation (the Turing machine) in 1936 intended as a means to refute a core part of Hilbert's program for the mechanization of mathematics, and that model set the bounds of what non-human computers can do.
  • "Hilbert and his famous problem" (2017) — DOI: 10.1093/oso/9780198747826.003.0014 — A chapter from The Turing Guide. In the 1930s, Turing, Gödel, Church, and others founded theoretical computer science by examining the meaning and limits of computation.
  • "Did Turing prove the undecidability of the halting problem?" (2026) — DOI: 10.1093/logcom/exaf075 — A paper examining the accuracy of the common attribution of the undecidability of the halting problem to Turing (1936), arriving at a nuanced conclusion.
Sources (15)
  • Introduction to Computer Science — 1.1 Computer Science
  • Introduction to Computer Science — 2.1 Computational Thinking
  • Introduction to Computer Science — 3.1 Introduction to Data Structures and Algorithms
  • Introduction to Computer Science — 3.2 Algorithm Design and Discovery
  • Introduction to Computer Science — 3.3 Formal Properties of Algorithms
  • Introduction to Computer Science — 3.4 Algorithmic Paradigms
  • Introduction to Computer Science — 3.5 Sample Algorithms by Problem
  • Teaching Computational Thinking UnpluggedDOI 10.4018/978-1-7998-4576-8.ch009
  • Generative AI to Foster Computational Thinking in Initial Teacher Education: A Thematic Literature Review and ModelDOI 10.20944/preprints202602.1017.v1
  • The Code-Centric Nature of Computational Thinking Education: A Review of Trends and Issues in Computational Thinking Education ResearchDOI 10.1177/21582440211016418
  • A PERFORMANCE COMPARISON OF SORTING ALGORITHMS IN DIFFERENT PROGRAMMING LANGUAGESDOI 10.28925/2663-4023.2023.21.8698
  • Analyzing the Halting Problem: Limits of Computation and Decidability in Turing MachinesDOI 10.20944/preprints202512.0580.v1
  • Decidability and the EntscheidungsproblemDOI 10.1093/oso/9780198747826.003.0049
  • Hilbert and his famous problemDOI 10.1093/oso/9780198747826.003.0014
  • Did Turing prove the undecidability of the halting problem?DOI 10.1093/logcom/exaf075
📚 Computers from Scratch — From a Braille Cell to a Parcel Sorting Hub
3 / 6
  1. 1.Bits and Data — Raised Dots and Flat Spots, a Code the Fingertips Know
  2. 2.CPU and Memory — A Desk That Gets Cleared, Library Stacks That Stay
  3. 3.Algorithms — Calling Numbers One by One, Questions That Erase Half
  4. 4.Programs and Programming Languages — A Score Written by People, a Piano That Plays Only the Holes
  5. 5.Operating Systems — The Caretaker Who Arrives First, the Meeting Room Everyone Takes Turns In
  6. 6.The Internet — Boxes Shipped in Pieces, a Sorting Hub at Every Fork
← PreviousCPU and Memory — A Desk That Gets Cleared, Library Stacks That StayNext →Programs and Programming Languages — A Score Written by People, a Piano That Plays Only the Holes

This article is AI-generated from research papers for general information and does not replace professional advice. Spotted an error? Let us know

© 2026 Neokuns (Paperis). Sharing links is welcome; republishing the full text requires prior permission.