Study guide

6.1 Searching Algorithms: Linear Search and Binary Search

Praxis Computer Science 5652

Track your progress as you read

Finished sections get a check mark.

1 Chapter 1: Praxis 5652 Exam Overview and ETS Pseudocode

1.1 Praxis 5652 Test Facts, Scoring, and Registration 1.2 Official ETS Pseudocode Notation and Tracing Strategy

2 Chapter 2: Impacts of Computing: Innovation, Access, and Effects

2.1 Computing for Creativity, Problem Solving, Communication, and Innovation 2.2 Equal Access, the Digital Divide, and Accessibility 2.3 Beneficial and Harmful Effects of Computing Innovations

3 Chapter 3: Impacts of Computing: Intellectual Property, Ethics, Privacy, and Security

3.1 Intellectual Property: Copyright, Open Source, and Creative Commons 3.2 Ethical and Unethical Computing Practices and Their Implications 3.3 Privacy, Security, Data Collection, and Local vs. Cloud Storage

4 Chapter 4: Algorithms and Computational Thinking: Abstraction, Decomposition, Number Bases, and Representation

4.1 Abstraction and Abstraction Hierarchies 4.2 Decomposition, Pattern Recognition, and Developing Algorithms 4.3 Number Bases: Binary, Octal, Decimal, and Hexadecimal 4.4 Algorithm Formats: Natural Language, Flowcharts, Pseudocode, and Tracing

5 Chapter 5: Algorithms: Efficiency, Limits of Computing, and Randomization

5.1 Algorithm Efficiency: Linear, Quadratic, Exponential, and Logarithmic Growth 5.2 Limits of Computing: Unsolvable Problems, Intractability, and Heuristics 5.3 Randomization, Random vs. Pseudorandom Numbers, and Scaling to a Range

6 Chapter 6: Algorithms: Searching, Sorting, and Recursion

6.1 Searching Algorithms: Linear Search and Binary Search 6.2 Sorting Algorithms: Tracing, Comparisons, Correctness, and Efficiency 6.3 Recursion: Base Cases, Tracing, Errors, and Iterative Equivalents

7 Chapter 7: Programming: Variables, Data Types, Strings, and Expressions

7.1 Variables, Data Types, and Type Conversion 7.2 Strings and String Operations 7.3 Operators, Precedence, Expressions, and Formulas 7.4 Boolean Expressions, Truth Tables, and Boolean Algebra

8 Chapter 8: Programming: Selection, Iteration, and Writing Code

8.1 Sequence and Selection: if, else, Chained and Nested Conditions 8.2 Iteration: for, while, do … while, and repeat … until Loops 8.3 Reading, Completing, and Modifying Code

9 Chapter 9: Programming: Procedures, Arrays, and Data Structures

9.1 Procedures, Parameters, Return Values, Nested Calls, and Scope 9.2 Arrays, Lists, and Two-Dimensional Arrays 9.3 Stacks, Queues, and Dictionaries (Maps)

10 Chapter 10: Programming: Correctness, Errors, Testing, and Code Quality

10.1 Program Correctness: Preconditions, Postconditions, Invariants, and Testing vs. Proof 10.2 Error Types and Debugging Techniques 10.3 Choosing Useful Test Cases: Boundaries, Partitions, Coverage, and Regression 10.4 Extensibility, Modifiability, and Reusability: Constants and Parameterization 10.5 Documentation, Code Reviews, Peer Feedback, and End-User Feedback

11 Chapter 11: Programming: Events, Usability, Input Validation, and APIs

11.1 Event-Driven Programming, Asynchronous Events, and Concurrency 11.2 Usability, Meaningful Error Messages, and Input Validation vs. Verification 11.3 Libraries and APIs: Reading Definitions, Making Calls, and Weighing Trade-offs

12 Chapter 12: Programming: Languages, Tools, Paradigms, and Object-Oriented Design

12.1 Low- and High-Level Languages, Compilers and Interpreters, and IDEs 12.2 Programming Paradigms: Procedural, Object-Oriented, and Others 12.3 Classes, Objects, Instance Variables, Methods, and Encapsulation 12.4 Inheritance, Polymorphism, and Overloading vs. Overriding

13 Chapter 13: Data: Bits, Encoding, Compression, and Encryption

13.1 Bits and Bytes: Why Binary, Storage Calculations, and Signed Integers 13.2 Encoding Text, Images, and Sound 13.3 Lossless and Lossy Compression: Run-Length Encoding, Huffman Coding, and Media Formats 13.4 Encoding vs. Encryption, Symmetric and Public-Key Encryption, and Their Trade-offs

14 Chapter 14: Data: Analysis Tools, Simulation, Storage, and Collection

14.1 Analyzing Data with Spreadsheets: Cleaning, Transforming, and Visualizing 14.2 Simulation and Modeling 14.3 Files, Databases, and Storage Requirements: Scale, Redundancy, and Backup 14.4 Collecting, Aggregating, and Generating Data: Public Data Sets, Surveys, Sensors, and Crowdsourcing

15 Chapter 15: Computing Systems: Hardware, Operating Systems, and Computing Environments

15.1 Hardware Components and the Fetch–Decode–Execute Cycle 15.2 Operating Systems, Software Components, and Resource Issues 15.3 Embedded Systems, the Internet of Things, and Types of Computing Systems 15.4 Local, Network, and Cloud Computing and Storage; How Binary Data Are Stored

16 Chapter 16: Networks, the Internet, the Web, and Cybersecurity

16.1 Network Types and Wired and Wireless Communication 16.2 Network Hardware and Layered Network Models (OSI and TCP/IP) 16.3 Network Performance: Bandwidth, Latency, Load, and Estimating Needs 16.4 How the Internet Works: Protocols, IP Addressing, DNS, URLs, and Reliability 16.5 The Web: HTTP, HTML and Markup Languages, Browsers, Servers, and Clients 16.6 Cybersecurity: The Five Pillars, Strong Passwords, Security Strategies, and Trade-offs

6.1 Searching Algorithms: Linear Search and Binary Search

Key Takeaways Explain This Topic AI

Linear search works on unsorted or sorted data; it examines k + 1 elements to find a target at index k and all n elements when the target is absent.

Binary search requires sorted data and random access by index; each comparison eliminates about half of the remaining elements.

Binary search examines at most ⌊log₂ n⌋ + 1 elements, which is 10 for 1,000 elements and 20 for 1,000,000 elements.

A correct binary search loops while low ≤ high and moves the bounds to mid + 1 or mid − 1, so the element just checked is excluded.

For a single search of unsorted data, linear search is best; sorting first pays off only when many searches will follow.

Last updated: September 2026

What this competency asks

ETS groups searching with sorting: understand searching and sorting algorithms; analyze searching algorithms for correctness and efficiency . For searching, you should be able to:

Trace algorithms and predict output and intermediate results.

Calculate the number of comparisons required for linear and binary search.

Linear (sequential) search

Linear search checks each element in order until it finds the target or runs out of elements. // returns the index of target in list, or -1 if it is absent

  • int linearSearch ( int[ ] list, int n, int target )
  • for ( int i ← 0; i < n; i ← i + 1 )
  • if ( list[i] == target )
  • return i
  • end if
  • end for
  • return -1
  • end linearSearch
  • Situation Elements examined
  • Target at index 0 (best case) 1
  • Target at index k k + 1
  • Target absent (worst case) n
  • Average, if every position is equally likely (n + 1) / 2

Linear search is O(n) . It needs no precondition : the data may be unsorted, and it works on structures that can only be walked in order, such as linked lists. If the list is known to be sorted, you can stop early once an element exceeds the target. That shortens unsuccessful searches, but the worst case is still O(n).

Binary search

Binary search works only on sorted data. It compares the target with the middle element of the current range and discards the half that cannot contain the target. // list is sorted in increasing order; first element at index 0

  • int binarySearch ( int[ ] list, int n, int target )
  • int low ← 0
  • int high ← n - 1
  • while ( low ≤ high )
  • int mid ← ( low + high ) / 2 // integer division
  • if ( list[mid] == target )
  • return mid
  • else
  • if ( list[mid] < target )
  • low ← mid + 1
  • else
  • high ← mid - 1
  • end if
  • end if
  • end while
  • return -1
  • end binarySearch
  • Worked trace
  • Sorted list (indexes 0–9): {3, 8, 12, 17, 23, 31, 38, 44, 50, 61}
  • Search for 44
  • low high mid list[mid] Decision
  • 0 9 4 23 23 < 44, so low ← 5
  • 5 9 7 44 Found; return 7

Two elements examined: 23 and 44.

Search for 20 (absent)

  • low high mid list[mid] Decision
  • 0 9 4 23 23 > 20, so high ← 3
  • 0 3 1 8 8 < 20, so low ← 2
  • 2 3 2 12 12 < 20, so low ← 3
  • 3 3 3 17 17 < 20, so low ← 4
  • 4 3 — — low > high; return −1

Four elements examined: 23, 8, 12, 17. For n = 10, the maximum is ⌊log₂ 10⌋ + 1 = 3 + 1 = 4 .

Counting comparisons

Each pass through the loop examines one element and at least halves the remaining range, so binary search examines at most ⌊log₂ n⌋ + 1 elements. This equals ⌈log₂(n + 1)⌉.

  • n Linear search, worst case Binary search, worst case
  • 10 10 4
  • 100 100 7
  • 1,000 1,000 10
  • 10,000 10,000 14
  • 1,000,000 1,000,000 20
  • 1,000,000,000 1,000,000,000 30

A quick way to calculate: find the smallest power of 2 that is greater than n , and use its exponent. For n = 1,000,000: 2¹⁹ = 524,288 ≤ n and 2²⁰ = 1,048,576 > n, so the maximum is 20. For exactly n = 16, 2⁴ = 16 is not greater than 16, so the maximum is 5.

Some questions count three-way comparisons ("equal, less, or greater?") as one comparison, as above. Others count each == and < test separately. Read the stem's definition.

Correctness details

Precondition: sorted data. On unsorted data, binary search can report that a present value is missing.

Loop condition low ≤ high . When low equals high, one element remains and must still be checked. Using < skips it.

Bounds mid + 1 and mid - 1 . The middle element was already checked. Setting low ← mid can cause an infinite loop when high = low + 1.

Duplicates. Standard binary search returns some matching index, not necessarily the first. Finding the first occurrence requires continuing to search the left half after a match.

Integer overflow. In languages with fixed-size integers, ( low + high ) / 2 can overflow for enormous arrays. low + ( high - low ) / 2 gives the same midpoint without the risk.

Choosing between them

  • Factor Linear search Binary search
  • Data must be sorted? No Yes
  • Needs index (random) access? No Yes
  • Worst case O(n) O(log n)
  • Best case 1 element 1 element
  • Simple to write correctly? Very Requires care with bounds

If the data are unsorted and you will search once , use linear search. Sorting first costs O(n log n), which is more than the O(n) search. If you will search many times, sort once and then use binary search. The sorting cost is spread across all the fast searches.

Loading diagram... Binary search: each comparison discards about half of the range