Revision Summary: Searching (NCERT Class 12 CS Chapter 6)
1. Chapter at a Glance
- Searching means locating a particular element (called key) in a collection of elements and determining its position if present.
- Linear search (also called sequential or serial search) compares the key with every element of the list one by one in the given order; it works on unsorted lists but requires up to n comparisons.
- Binary search requires the list to be sorted (ascending/descending for numbers or alphabetical for text) and repeatedly halves the search area by comparing the key with the middle element.
- In binary search, an unsuccessful comparison still reveals whether the key lies in the first or second half, allowing the search area to be reduced by half each time.
- Hashing uses a hash function to compute the exact index of a key in one step, making search time independent of list size (provided no collision occurs).
- A hash function (example: remainder method h(element) = element % size) maps each element to an index in the hash table.
- Collision occurs when two or more elements map to the same slot in the hash table; a perfect hash function maps every key to a unique index and never produces collision.
- Binary and hashing techniques are more efficient than linear search when applicable, but binary search needs a sorted list and hashing needs a suitable hash function.
2. Key Terms and Definitions
- Searching: Locating a particular element (key) in a collection of elements; result indicates presence/absence and position if present.
- Linear search / Sequential search / Serial search: Exhaustive technique that compares the key with each element of the list one by one in order, starting from the first element.
- Binary search: Search technique that uses ordering of elements; repeatedly compares the key with the middle element and discards half the list each time.
- Hashing: Technique that computes the index of a key directly using a hash function so that presence can be checked in one comparison.
- Hash function: Formula that takes an element and generates an index value for placement in the hash table (example given: remainder method).
- Hash table: New list created by applying the hash function; each index holds at most one item and positions are indexed from 0.
- Collision: Situation when two or more elements of the list map to the same index/slot in the hash table.
- Collision resolution: Process of placing additional items that hash to the same slot (beyond scope of chapter).
- Perfect hash function: Hash function that maps every input key to a unique index in the hash table; collision never occurs.
3. Syntax and Constructs
Linear search function
General form:
python
def linearSearch(list, key):
for index in range(0, len(list)):
if list[index] == key:
return index + 1
return None
Example: position = linearSearch(list1, 23)
Binary search function
General form:
python
def binarySearch(list, key):
first = 0
last = len(list) - 1
while first <= last:
mid = (first + last) // 2
if list[mid] == key:
return mid
elif key > list[mid]:
first = mid + 1
else:
last = mid - 1
return -1
Example: pos = binarySearch(list1, 4)
Hash find function (remainder method)
General form:
python
def hashFind(key, hashTable):
if hashTable[key % 10] == key:
return (key % 10) + 1
else:
return None
Example: position = hashFind(16, hashTable)
Creating hash table (remainder method)
General form: hashTable[L[i] % 10] = L[i]
Example: hashTable[34 % 10] = 34
4. Algorithms and Worked Logic
Linear Search (Algorithm 6.1)
LinearSearch(numList, key, n)
Step 1: SET index = 0
Step 2: WHILE index < n, REPEAT Step 3
Step 3: IF numList[index] == key THEN
PRINT “Element found at position”, index+1; STOP
ELSE index = index + 1
Step 4: PRINT “Search unsuccessful”
- Always performs n comparisons when key is absent or at the end; minimum 1 comparison when key is first.
Binary Search (Algorithm 6.2)
BinarySearch(numList, key)
Step 1: SET first = 0, last = n-1
Step 2: Calculate mid = (first + last) // 2
Step 3: WHILE first <= last REPEAT Step 4
Step 4: IF numList[mid] == key THEN
PRINT “Element found at position”, mid+1; STOP
ELSE IF numList[mid] > key THEN last = mid - 1
ELSE first = mid + 1
Step 5: PRINT “Search unsuccessful”
- Uses floor division //; each unsuccessful comparison halves the remaining list.
- Requires sorted list; returns position or declares unsuccessful after narrowing to one element.
Hashing search logic
- Compute index = key % size(hashTable)
- Compare hashTable[index] with key (one comparison only).
5. Common Errors and Exam Pitfalls
- Forgetting that binary search requires the list to be sorted beforehand (text repeatedly stresses this).
- Using
/ instead of // for mid calculation when list size is even (NCERT specifies floor division and that mid element is at index 5 for 10 elements).
- Not updating first/last correctly after each binary search iteration, leading to infinite loop or missed elements.
- Assuming linear search stops early when key is absent (it always scans entire list).
- Ignoring that hashing search time is constant only when a perfect hash function is used and no collision occurs.
- In programs, returning
None/-1 incorrectly or forgetting to add 1 when converting 0-based index to 1-based position for output.
- Writing code that modifies the original list during binary search (text states the algorithm only changes search indices).