Chapter 6: Searching

CBSE Unit: NOT explicitly in current CBSE syllabus (2025-26) as a separate topic Status: Supplementary, linear search is covered in Class XI (lists), binary search is fundamental Priority: PREPARE, searching is a core CS concept, useful for practical exam

---

Key Concepts

6.1 What is Searching?

• Locating a particular element (key) in a collection, Result: found (with position) or not found, Two main techniques: Linear Search and Binary Search
• Searching is one of the most fundamental operations in computer science

---

6.2 Linear Search (Sequential Search)

Concept, Compare key with each element one by one, from first to last, Works on unsorted and sorted lists, Simple but slow for large lists, Also works on lists of strings, tuples, or any comparable data

Algorithm

For index = 0 to n-1:
    If list[index] == key:
        Return index (found)
Return "Not found"

Python Implementation

def linear_search(lst, key):
    for index in range(len(lst)):
        if lst[index] == key:
            return index + 1    # position (1-based)
    return None                 # not found

list1 = [8, -4, 7, 17, 0, 2, 19]
pos = linear_search(list1, 17)
if pos:
    print(f"Found at position {pos}")  # Found at position 4
else:
    print("Not found")

Dry Run Trace: Linear Search

Search for 17 in [8, -4, 7, 17, 0, 2, 19]

Step	index	list[index]	list[index] == 17?	Action
1	0	8	No	Continue
2	1	-4	No	Continue
3	2	7	No	Continue
4	3	17	Yes	Return 4 (position)

Result: Found at position 4 (4 comparisons)

Search for 5 in [8, -4, 7, 17, 0, 2, 19] (element NOT present)

Step	index	list[index]	list[index] == 5?	Action
1	0	8	No	Continue
2	1	-4	No	Continue
3	2	7	No	Continue
4	3	17	No	Continue
5	4	0	No	Continue
6	5	2	No	Continue
7	6	19	No	Continue
-	-	End of list	-	Return None

Result: Not found (7 comparisons, checked every element)

Linear Search on Strings

def linear_search_string(lst, key):
    """Search for a string in a list (case-insensitive)"""
    for index in range(len(lst)):
        if lst[index].lower() == key.lower():
            return index + 1
    return None

cities = ["Delhi", "Mumbai", "Chennai", "Kolkata", "Bangalore"]
pos = linear_search_string(cities, "chennai")
if pos:
    print(f"Found at position {pos}")  # Found at position 3
else:
    print("Not found")

Dry run: Search for "chennai" in ["Delhi", "Mumbai", "Chennai", "Kolkata", "Bangalore"]

Step	index	lst[index]	Match?	Action
1	0	"Delhi" -> "delhi"	"delhi" == "chennai"? No	Continue
2	1	"Mumbai" -> "mumbai"	"mumbai" == "chennai"? No	Continue
3	2	"Chennai" -> "chennai"	"chennai" == "chennai"? Yes	Return 3

Result: Found at position 3

Counting Occurrences with Linear Search

def count_occurrences(lst, key):
    """Count how many times key appears in the list"""
    count = 0
    positions = []
    for i in range(len(lst)):
        if lst[i] == key:
            count += 1
            positions.append(i + 1)  # 1-based positions
    return count, positions

marks = [85, 90, 85, 78, 92, 85, 88]
count, pos = count_occurrences(marks, 85)
print(f"85 appears {count} times at positions {pos}")
# 85 appears 3 times at positions [1, 3, 6]

Time Complexity

• Best case: O(1), key is the first element
• Worst case: O(n), key is last element or not present
• Average case: O(n/2) ~ O(n)

---

6.3 Binary Search

Concept, Works ONLY on sorted lists, Compares key with middle element, If match -> found, If key < middle -> search left half, If key > middle -> search right half, Each comparison halves the search area, very efficient

Algorithm

first = 0, last = n-1
While first <= last:
    mid = (first + last) // 2
    If list[mid] == key: found at mid
    Elif list[mid] > key: last = mid - 1  (search left)
    Else: first = mid + 1                 (search right)
Return "Not found"

Python Implementation

def binary_search(lst, key):
    first = 0
    last = len(lst) - 1
    while first <= last:
        mid = (first + last) // 2
        if lst[mid] == key:
            return mid + 1          # position (1-based)
        elif lst[mid] > key:
            last = mid - 1          # search left half
        else:
            first = mid + 1         # search right half
    return None                     # not found

sorted_list = [2, 3, 5, 7, 10, 11, 12, 17, 19, 23, 29, 31, 37, 41, 43]
pos = binary_search(sorted_list, 17)
print(f"Found at position {pos}")   # Found at position 8

Dry Run Trace 1: Search for 17 in [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]

(Odd-length list: 15 elements)

Iteration	first	last	mid = (first+last)//2	list[mid]	Action
1	0	14	7	17	17 == 17, FOUND at position 8!

Result: Found in just 1 comparison!

Dry Run Trace 2: Search for 43 in [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]

Iteration	first	last	mid	list[mid]	Action
1	0	14	7	17	43 > 17, search right: first = 8
2	8	14	11	31	43 > 31, search right: first = 12
3	12	14	13	41	43 > 41, search right: first = 14
4	14	14	14	43	43 == 43, FOUND at position 15!

Result: Found in 4 comparisons (instead of 15 with linear search)

Dry Run Trace 3: Search for 2 in [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]

Iteration	first	last	mid	list[mid]	Action
1	0	14	7	17	2 < 17, search left: last = 6
2	0	6	3	7	2 < 7, search left: last = 2
3	0	2	1	3	2 < 3, search left: last = 0
4	0	0	0	2	2 == 2, FOUND at position 1!

Result: Found in 4 comparisons

Dry Run Trace 4: Search for 15 (NOT present) in [2,3,5,7,10,11,12,17,19,23,29,31,37,41,43]

Iteration	first	last	mid	list[mid]	Action
1	0	14	7	17	15 < 17, search left: last = 6
2	0	6	3	7	15 > 7, search right: first = 4
3	4	6	5	11	15 > 11, search right: first = 6
4	6	6	6	12	15 > 12, search right: first = 7
5	7	6	-	-	first > last, EXIT LOOP

Result: Not found (5 comparisons to confirm absence)

Dry Run Trace 5: Even-length list

Search for 30 in [5, 10, 20, 25, 30, 35, 40, 50] (8 elements)

Iteration	first	last	mid = (first+last)//2	list[mid]	Action
1	0	7	3	25	30 > 25, search right: first = 4
2	4	7	5	35	30 < 35, search left: last = 4
3	4	4	4	30	30 == 30, FOUND at position 5!

Note for even-length list: mid = (0+7)//2 = 3 (floor division always gives the left-of-center element)

Dry Run Trace 6: Even-length list, element not present

Search for 27 in [5, 10, 20, 25, 30, 35, 40, 50] (8 elements)

Iteration	first	last	mid	list[mid]	Action
1	0	7	3	25	27 > 25, search right: first = 4
2	4	7	5	35	27 < 35, search left: last = 4
3	4	4	4	30	27 < 30, search left: last = 3
4	4	3	-	-	first > last, EXIT LOOP

Result: Not found (3 comparisons)

Binary Search on Strings

Binary search works on sorted lists of strings too (lexicographic comparison):

def binary_search_string(lst, key):
    """Binary search in a sorted list of strings"""
    first = 0
    last = len(lst) - 1
    while first <= last:
        mid = (first + last) // 2
        if lst[mid].lower() == key.lower():
            return mid + 1
        elif lst[mid].lower() > key.lower():
            last = mid - 1
        else:
            first = mid + 1
    return None

# List MUST be sorted alphabetically
cities = ["Bangalore", "Chennai", "Delhi", "Kolkata", "Mumbai"]
pos = binary_search_string(cities, "Delhi")
if pos:
    print(f"Found at position {pos}")  # Found at position 3

Dry run: Search for "Delhi" in ["Bangalore", "Chennai", "Delhi", "Kolkata", "Mumbai"]

Iteration	first	last	mid	lst[mid]	Action
1	0	4	2	"Delhi"	"delhi" == "delhi", FOUND at position 3!

Binary Search (Recursive Version)

def binary_search_recursive(lst, key, first, last):
    if first > last:
        return None
    mid = (first + last) // 2
    if lst[mid] == key:
        return mid + 1
    elif lst[mid] > key:
        return binary_search_recursive(lst, key, first, mid - 1)
    else:
        return binary_search_recursive(lst, key, mid + 1, last)

sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
pos = binary_search_recursive(sorted_list, 23, 0, len(sorted_list) - 1)
print(f"Found at position {pos}")  # Found at position 6

Time Complexity

• Best case: O(1), key is the middle element
• Worst case: O(log n), key is at extreme end or not present, Much faster than linear search for large sorted lists

How log2(n) works:

n (list size)	Max comparisons (log2 n)
8	3
16	4
32	5
64	6
128	7
256	8
1,000	~10
1,000,000	~20
1,000,000,000	~30

Binary search can find an element in a billion-element sorted list in just ~30 comparisons!

---

6.4 Comparison

Feature	Linear Search	Binary Search
List requirement	Any (sorted or unsorted)	Must be sorted
Approach	Sequential, one by one	Divide and conquer
Best case	O(1)	O(1)
Worst case	O(n)	O(log n)
Average case	O(n)	O(log n)
For 1000 elements worst case	1000 comparisons	~10 comparisons
For 1,000,000 elements	1,000,000 comparisons	~20 comparisons
Implementation	Simple	Slightly more complex
Works on strings?	Yes	Yes (if sorted)
Modifies the list?	No	No
Extra memory	None	None (iterative)

When to use which:

• Linear search: unsorted list, small list, search once or rarely
• Binary search: sorted list, large list, search frequently (worth the cost of sorting first)

---

6.5 Combined Example: Sort Then Search

In practice, if you need to search multiple times, sort the list first, then use binary search:

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(0, n - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

def binary_search(lst, key):
    first = 0
    last = len(lst) - 1
    while first <= last:
        mid = (first + last) // 2
        if lst[mid] == key:
            return mid + 1
        elif lst[mid] > key:
            last = mid - 1
        else:
            first = mid + 1
    return None

# Unsorted list
marks = [78, 92, 56, 88, 45, 73, 91, 62, 85, 70]
print("Original:", marks)

# Sort first
bubble_sort(marks)
print("Sorted:", marks)

# Now search efficiently
key = int(input("Enter marks to search: "))
pos = binary_search(marks, key)
if pos:
    print(f"Found at position {pos} in sorted list")
else:
    print("Not found")

---

6.6 Search by Hashing (Advanced), Uses a hash function to compute index from key value, Direct access, O(1) average time

• Collision: when two keys map to same index, Collision resolution: chaining, open addressing, Not typically asked in CBSE, but good to know

---

Practice Problems

Short answer:

1. What is the main advantage of binary search over linear search?
2. Why does binary search require the list to be sorted?
3. What is the maximum number of comparisons needed to search for an element in a sorted list of 1024 elements using binary search? (Answer: log2(1024) = 10)
4. Can linear search be used on a list of strings? Give an example.

Tracing:

1. Trace binary search for key=7 in [1, 3, 5, 7, 9, 11, 13, 15]. Show first, last, mid at each step.
2. Trace binary search for key=6 in [2, 4, 6, 8, 10, 12]. (Even-length list)
3. Trace binary search for key=50 in [10, 20, 30, 40]. (Element not present)
4. Trace linear search for key="Mango" in ["Apple", "Banana", "Grapes", "Mango", "Orange"].

Programming:

1. Write a function that uses linear search to find the first and last occurrence of an element.
2. Modify binary search to work on a list sorted in descending order.
3. Write a program that searches for a student name in a sorted list of names and returns their roll number.
4. Write a program that counts how many comparisons binary search makes for a given key.

Solutions for selected problems:

Binary search for key=7 in [1, 3, 5, 7, 9, 11, 13, 15]:

Iteration	first	last	mid	list[mid]	Action
1	0	7	3	7	7 == 7, FOUND at position 4!

Binary search for key=6 in [2, 4, 6, 8, 10, 12]:

Iteration	first	last	mid	list[mid]	Action
1	0	5	2	6	6 == 6, FOUND at position 3!

Binary search for key=50 in [10, 20, 30, 40]:

Iteration	first	last	mid	list[mid]	Action
1	0	3	1	20	50 > 20, first = 2
2	2	3	2	30	50 > 30, first = 3
3	3	3	3	40	50 > 40, first = 4
4	4	3	-	-	first > last, NOT FOUND

Binary search on descending sorted list:

def binary_search_desc(lst, key):
    """Binary search on a list sorted in descending order"""
    first = 0
    last = len(lst) - 1
    while first <= last:
        mid = (first + last) // 2
        if lst[mid] == key:
            return mid + 1
        elif lst[mid] < key:     # flip: < instead of >
            last = mid - 1       # search LEFT (larger values)
        else:
            first = mid + 1      # search RIGHT (smaller values)
    return None

desc_list = [91, 85, 72, 56, 38, 23, 16, 12, 8, 5, 2]
pos = binary_search_desc(desc_list, 56)
print(f"Found at position {pos}")  # Found at position 4

Count comparisons in binary search:

def binary_search_count(lst, key):
    """Binary search that also counts comparisons"""
    first = 0
    last = len(lst) - 1
    comparisons = 0
    while first <= last:
        mid = (first + last) // 2
        comparisons += 1
        if lst[mid] == key:
            return mid + 1, comparisons
        elif lst[mid] > key:
            last = mid - 1
        else:
            first = mid + 1
    return None, comparisons

sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
pos, comp = binary_search_count(sorted_list, 23)
print(f"Found at position {pos}, comparisons: {comp}")
# Found at position 6, comparisons: 4

pos, comp = binary_search_count(sorted_list, 50)
print(f"Position: {pos}, comparisons: {comp}")
# Position: None, comparisons: 4

---

Key Points Students Miss

1. Binary search REQUIRES sorted list, forgetting to sort first is the #1 mistake
2. mid = (first + last) // 2 - use floor division, not regular division
3. Binary search does NOT modify the list, only the index variables (first, last, mid) change
4. For n elements: linear search = n comparisons max, binary search = log2(n) comparisons max
5. For 1 million elements: linear = 1,000,000 comparisons, binary = ~20 comparisons
6. Even-length list: middle is calculated using // (floor division), always takes the left-of-center index
7. The loop condition is first <= last (not first < last), the = is crucial for single-element checks
8. When the element is not found, binary search exits when first > last
9. Linear search works on ANY data type that supports == comparison
10. Binary search on strings requires the list to be alphabetically sorted

---

Board Exam Tips

1. For binary search tracing questions, always show first, last, mid at each iteration, this is what examiners look for
2. If asked "which search is better", the answer depends on context, mention both pros and cons
3. Know both the iterative and the concept of recursive binary search
4. The formula mid = (first + last) // 2 must use floor division, writing / instead of // will give wrong results
5. If asked about time complexity, express it as O(n) for linear and O(log n) for binary, and explain what log means (number of times you can halve n)
6. Common 1-mark question: "Binary search requires the list to be ____" (Answer: sorted)