Cheat sheet · Class 12 · CBSE · Science Computer Science
Searching cheat sheet
The whole chapter on one page: key formulas, facts and the points to remember, for quick revision before a test.
CBSE Class 12 · Computer Science
Cheat sheet
Chapter 8Searching
Binary search needs a sorted list and halves it every step.
1. Techniques
| Search | Needs | Time |
|---|---|---|
| Linear | any list | O(n) |
| Binary | sorted list | O(log n) |
| Hashing | hash table | O(1) average |
2. Binary Search
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == key: return mid
elif a[mid] < key: lo = mid + 1
else: hi = mid - 1
return -1
3. Hashing
- Hash function maps a key to an index (e.g. key % size).
- Collision: two keys, same index — handled by chaining or probing.
4. Key Points
- Linear search best case: first element.
- 1 000 sorted items: ≤ 10 binary steps.
- Python dicts use hashing.
- Binary search fails on unsorted data.
Remember: Linear vs binary vs hashing | binary search code
Searching: questions and notes
More Class 12 · CBSE · Science Computer Science cheat sheets
Practise Searching
Sign up free to practise the full chapter. Questions you get wrong come back until you've mastered them.
Start practising freeFree to start · No credit card needed