Worksheets › Class 12 › Searching › Cheat sheet
Class 12 Searching: cheat sheet
CBSE Computer Science. Linear search, binary search with its mid points as the textbook codes it, the comparisons each makes, and hashing by the remainder method with collisions.
Key ideas
- Linear search compares the key with each item from the left; it works on any list and makes all n comparisons when the key is missing.
- The textbook’s linear search gives the position counting from 1, which is the index + 1.
- Binary search needs a sorted list: compare the key with the middle item and keep only the half that can hold it.
- mid = (first + last) // 2; if L[mid] > key then last = mid − 1, if smaller then first = mid + 1; when first > last the key is not there.
- Hashing stores a key at index key % size of the table, so one look finds it; two keys with the same remainder collide.
Remember
| Linear search | comparisons = the position of the key, or n if it is missing |
| Binary search | L = [4, 9, 15, 22, 30, 41, 56], key 41: mid 3 (22 is smaller), then mid 5 (41): 2 comparisons |
| Most comparisons, n items | the whole part of log₂ n, plus 1: 7 items → 3, 100 → 7, 1,000 → 10 |
| Hash function | h(key) = key % size: 47 % 10 = 7, and 57 % 10 = 7 too, a collision |
| Comparing the two | linear: up to n; binary: up to about log₂ n, but only on a sorted list |
Watch out
- Using binary search on a list that is not sorted.
- Writing mid = (first + last) / 2: that is a float in Python and cannot be an index.
- Counting positions from 0 when the textbook’s linear search counts from 1.
- Forgetting that a missing key costs linear search all n comparisons.
Worked example
What does this print? L = [7, 17, 21, 27, 33, 36, 47, 71, 81, 83, 87, 98] key = 87 first, last = 0, len(L) - 1 count = 0 pos = None while first <= last: mid = (first + last) // 2 count = count + 1 if L[mid] == key: pos = mid break elif L[mid] > key: last = mid - 1 else: first = mid + 1 print(pos, count)
Working: pos stays None when the key is not found; count is the number of passes
Answer: 10 3
Practise Searching
Revise with this page, then practise: every Searching sheet in the app is new, with an answer key and working.
Coming soon for Android and iPhone.