Linear and Binary Search
Linear search checks elements sequentially until it finds the target or exhausts the collection.
Summary
Linear search checks elements sequentially until it finds the target or exhausts the collection. Binary search compares the target with a midpoint element and uses sorted order to discard half the remaining candidates.
| Property | Linear search | Standard binary search |
|---|---|---|
| Requirements | No sorted order or efficient indexing needed | Sorted data and constant-time indexed access for logarithmic time |
| Worst-case time | ||
| Best-case time |
🧠 Key Concepts
- Linear search
- Binary search
- Sorted order
- Indexed access
- Midpoint calculation
- Inclusive bounds
- Auxiliary space
- Duplicate values
🧠 Quick Check
See what you remember from the summary.
An unsorted collection has no efficient indexed access, and only one lookup is needed. What is the most suitable approach described in the notes?
🧠 Flashcards Preview
Tap a card to reveal the definition.
Ready to quiz yourself?
Test what you remember with a full practice quiz on this note. Create a free account and start in seconds.
Full Notes
Read the original note content before deciding whether to save or study from it.
Linear and Binary Search
📘 Overview Linear search examines elements sequentially, whereas binary search repeatedly halves a sorted search interval. Their worst-case running times are and respectively, where is the number of elements.
🧠 Key Idea Binary search gains efficiency by using sorted order to eliminate half the remaining candidates after each comparison. Linear search needs no sorted order and works directly on sequential collections.
More ways to study when you copy this note
Copy this note into your library to unlock focused practice sessions and long-term review.
Answer all questions first, then see feedback at the end — the way real exams work.
Focuses each session on what you got wrong, not what you already know.
Full timed exam with all questions, no pausing, and results at the end. Built for board exam prep.
Part of 🗄️ BS Information Systems — 1st Year
Browse this Review Set →More Computer Engineering notes
See all →More in Data Structures and Algorithms
See all →More from NoteLib
Browse NoteLib's public notes →Copy this note to your library and get the full Study Pack instantly — summary, key concepts, and practice quiz included.