Home
School Syllabus
CBSE
Class XII
Computer Science
अध्याय 6: खोज विधियां (Searching)

माध्यम चुनें / Select Medium:

CBSE • कक्षा XII • Computer Science • अध्याय 6

अनुमानित समय: 45 Mins

प्रगति: अध्ययनरत

खोज विधियां (Searching)

In CBSE Class 12 Computer Science, "Searching" provides an authoritative, mathematically rigorous master study resource on algorithm efficiency and element retrieval. This comprehensive chapter contrasts Linear Search (sequential scanning on unordered datasets) with Binary Search (logarithmic divide-and-conquer on pre-sorted arrays). It covers loop boundary mechanics, mid-point calculation algorithms, step-by-step trace tables, worst-case and best-case asymptotic time complexities ($O(n)$ vs $O(\log_2 n)$), recursive vs iterative binary search, and search optimization trade-offs aligned with the 2026–27 CBSE curriculum.

अध्याय CBT ऑनलाइन टेस्ट दें सभी अध्याय देखें

प्रस्तावना अध्याय अवधारणाएँ सिंटेक्स एवं प्रमुख कमांड अध्याय सारांश स्व-मूल्यांकन अभ्यास टेस्ट दें

How Can Google or a Bank Locate One User Among 8 Billion People in Just 33 Steps?

Imagine searching for a specific name in an unsorted directory of all 8 billion human beings on Earth. If you checked people one by one from top to bottom (Linear Search), you would have to perform an average of 4 billion comparisons. If each check took a millisecond, the search would take over 46 days! But if that same list of 8 billion names is sorted alphabetically, you can divide the phonebook in half, eliminate 4 billion names in the first step, eliminate 2 billion in the second step, and find any person on Earth in at most 33 comparisons using Binary Search! (Because $2^{33} \approx 8.58 \times 10^9$). How does logarithmic divide-and-conquer turn an impossible search into a fraction of a millisecond? This chapter masters linear and binary searching.

यह अध्याय क्यों महत्वपूर्ण है

Searching is the most frequent operation performed in software engineering. Every web query, database index lookup, cache retrieval, and dictionary key access relies on search algorithms. Understanding the mathematical gulf between linear $O(n)$ and logarithmic $O(\log n)$ time complexity demonstrates why sorting data upfront is one of the most profitable investments in computer science.

अध्ययन से पूर्व (आवश्यक ज्ञान)

Python lists, list indexing, and loops (`for`, `while`).
Basic logarithms: $\log_2(n)$ as the number of times $n$ can be divided by 2 before reaching 1.
Understanding conditional statements and integer floor division (`//`).

इस अध्याय के लक्ष्य

Implement Linear Search and evaluate its performance on unordered collections.
Formulate the Binary Search algorithm using the divide-and-conquer paradigm on sorted collections.
Trace binary search steps using low, high, and mid index trace tables.
Calculate asymptotic time complexities: Linear Search $O(n)$ vs Binary Search $O(\log_2 n)$.
Analyze the prerequisite requirement of sorted order for Binary Search.
Implement both Iterative and Recursive formulations of Binary Search in Python.
Evaluate the break-even trade-off: when is it faster to use linear search versus sorting and binary searching?

अध्याय रूपरेखा एवं प्रगति

1 1. Linear Search: Sequential Traver...

2 2. Binary Search: Logarithmic Divid...

3 3. Mathematical Analysis: Why Binar...

सम्पूर्ण सैद्धांतिक एवं वैचारिक अध्ययन

1. Linear Search: Sequential Traversal

Understand

Linear Search (Sequential Search) compares the target key sequentially with each element in the list from the first index ($0$) to the last ($n-1$) until either the key is located or the end of the collection is reached:

def linear_search(lst, target):
    """Searches for target in unsorted list. Returns index or -1."""
    for i in range(len(lst)):
        if lst[i] == target:
            return i  # Key found at index i!
    return -1         # Key not present in list

Complexity:

Best-case: $O(1)$ when the target is at index 0 (first comparison).
Worst-case: $O(n)$ when the target is at the final index $n-1$ or not present at all ($n$ comparisons).
Average-case: $O(n)$ (approx. $\frac{n+1}{2}$ comparisons).
Advantage: Works on completely unordered, unsorted datasets.

2. Binary Search: Logarithmic Divide-and-Conquer

Understand & Mathematics

Binary Search is an ultra-fast search algorithm that operates strictly on SORTED arrays using the Divide-and-Conquer paradigm. In each iteration, it compares the target with the middle element, eliminating half of the remaining search space:

Algorithm Mechanics:

Set pointers: `low = 0`, `high = len(lst) - 1`.
While `low <= high`:
- Calculate mid: `mid = (low + high) // 2`.
- If `lst[mid] == target`: Success! Return `mid`.
- If `target < lst[mid]`: Search left half by setting `high = mid - 1`.
- If `target > lst[mid]`: Search right half by setting `low = mid + 1`.
If `low > high`: Target is not in list; return `-1`.

Iterative Binary Search Implementation in Python:

def binary_search(sorted_lst, target):
    low = 0
    high = len(sorted_lst) - 1

    while low <= high:
        mid = (low + high) // 2
        if sorted_lst[mid] == target:
            return mid  # Target found!
        elif target < sorted_lst[mid]:
            high = mid - 1  # Discard right half
        else:
            low = mid + 1   # Discard left half
    return -1  # Target not found

3. Mathematical Analysis: Why Binary Search Scales to Billions

Mathematics & Complexity

In each step of Binary Search, the search space is halved: $\frac{n}{2}, \frac{n}{4}, \frac{n}{8}, \dots, \frac{n}{2^k}$. The algorithm terminates when the search space reduces to $1$ element:

$$\frac{n}{2^k} = 1 \implies 2^k = n \implies k = \log_2(n)$$

Therefore, the maximum number of comparisons for an array of size $n$ is $\lceil \log_2(n) \rceil + 1$:

Dataset Size ($n$)	Linear Search Worst Case ($n$)	Binary Search Worst Case ($\approx \log_2 n$)	Speedup Factor
1,000 (Thousand)	1,000 steps	10 steps	100× faster
1,000,000 (Million)	1,000,000 steps	20 steps	50,000× faster
1,000,000,000 (Billion)	1,000,000,000 steps	30 steps	33,333,333× faster!

प्रोग्रामिंग सिंटेक्स, स्टेटमेंट्स एवं भाषा अनुवादक नियम

Binary Search Max Steps

$$k = \lceil \log_2(n) \rceil$$

Number of comparisons in worst-case binary search.

Mid Index Calculation

$$\text{mid} = \text{low} + \frac{\text{high} - \text{low}}{2} \equiv (\text{low} + \text{high}) // 2$$

Integer floor division preventing overflow.

Linear vs Binary Search Halving Architecture

अध्याय का सार संक्षेप एवं 10 मुख्य निष्कर्ष

मुख्य बिंदु 1

Linear search checks elements sequentially from index 0 to n-1 in $O(n)$ time on unsorted collections.

मुख्य बिंदु 2

Binary search operates on pre-sorted arrays using divide-and-conquer, eliminating half the search space per comparison.

मुख्य बिंदु 3

Binary search maintains `low`, `high`, and `mid = (low + high) // 2` index pointers.

मुख्य बिंदु 4

If target < lst[mid], the search shifts left by setting `high = mid - 1`.

मुख्य बिंदु 5

If target > lst[mid], the search shifts right by setting `low = mid + 1`.

मुख्य बिंदु 6

The loop terminates successfully when `lst[mid] == target` or with failure when `low > high`.

मुख्य बिंदु 7

Binary search achieves logarithmic time complexity $O(\log_2 n)$, requiring at most 30 comparisons for 1 billion items.

मुख्य बिंदु 8

Linear search is preferred for small lists ($n < 20$) or single searches where the overhead of sorting ($O(n \log n)$) is not justified.

मुख्य बिंदु 9

For repeated searches, sorting once ($O(n \log n)$) followed by multiple binary searches ($O(\log n)$) provides massive speedups.

मुख्य बिंदु 10

Binary search can be implemented both iteratively using a while loop and recursively.

स्व-मूल्यांकन अभ्यास (Check Your Understanding)

मूल वैचारिक स्पष्टता की जांच के लिए नैदानिक प्रश्न। पहले स्वयं हल करें, फिर उत्तर देखें।

What is the indispensable prerequisite condition for applying Binary Search to a dataset?

उत्तर एवं व्याख्या देखें

उत्तर:

The dataset (list or array) MUST be strictly sorted in either ascending or descending order. If the list is unsorted, the assumption that elements to the left of mid are smaller and elements to the right are larger is violated, causing binary search to eliminate sections containing the target and producing incorrect failure results.

The list must be sorted; otherwise the left/right division logic fails.

Trace the step-by-step execution of Binary Search for `target = 67` on the sorted list:
`lst = [12, 24, 32, 45, 56, 67, 78, 89, 99]`
Show values of `low`, `high`, `mid`, and `lst[mid]` for each iteration.

उत्तर एवं व्याख्या देखें

उत्तर:

Initial List length $n = 9$. Indices $0$ to $8$. Target $= 67$.
• Iteration 1: low = 0, high = 8. mid = (0 + 8) // 2 = 4. lst[4] = 56. Since $67 > 56$, target is in right half → set low = mid + 1 = 5.
• Iteration 2: low = 5, high = 8. mid = (5 + 8) // 2 = 6. lst[6] = 78. Since $67 < 78$, target is in left half → set high = mid - 1 = 5.
• Iteration 3: low = 5, high = 5. mid = (5 + 5) // 2 = 5. lst[5] = 67. Target matched! Return index 5.
Search succeeded in exactly 3 comparisons!

Track low, high, mid in a table. Compare target against lst[mid] each step.

Calculate the maximum number of comparisons required to search for an element using Binary Search in a sorted array containing 1,048,576 ($2^{20}$) elements.

उत्तर एवं व्याख्या देखें

उत्तर: For an array of size $n$, the maximum number of comparisons in binary search is given by $\lceil \log_2 n \rceil + 1$.
For $n = 2^{20} = 1,048,576$:
$$\log_2(2^{20}) = 20\text{ divisions}$$
Maximum comparisons $= 20 + 1 = 21$ comparisons.
(In contrast, Linear Search would require over 1,000,000 comparisons in the worst case!)
log2(2^20) = 20 comparisons (at most 21 checks).

When is Linear Search preferred over Binary Search in software engineering?

उत्तर एवं व्याख्या देखें

उत्तर:

Linear search is preferred in two primary scenarios:
1. When the dataset is completely unsorted and only a single search is being conducted. (Sorting the list takes $O(n \log n)$ time, which is much slower than a single $O(n)$ linear search).
2. When the dataset is extremely small (e.g., $n < 15$), where the simplicity of linear search has less CPU branching overhead.

For unsorted data with a single search, or for very small arrays.

What happens in Binary Search when the target element is NOT present in the list? What is the termination condition?

उत्तर एवं व्याख्या देखें

उत्तर: When the target element is not present, the `low` and `high` pointers continually adjust toward each other until they converge on the same index (`low == high`). If the element at that index is not the target, the pointer moves one step further, causing `low` to become strictly greater than `high` (`low > high`). The `while low <= high:` loop terminates, and the function returns `-1` (indicating element not found).
Terminates when low > high, indicating the search space has shrunk to zero.

Why is `mid = (low + high) // 2` sometimes rewritten as `mid = low + (high - low) // 2` in programming languages like C++ and Java?

उत्तर एवं व्याख्या देखें

उत्तर:

In languages with fixed-width integer types (like 32-bit signed integers in C++ or Java, where the maximum value is $2^{31} - 1 = 2,147,483,647$), if low and high are both large numbers (e.g., both around $1.5$ billion), their sum low + high equals $3$ billion, causing an integer arithmetic overflow that wraps around to a negative number. Writing low + (high - low) // 2 is mathematically identical but guarantees that intermediate calculations never exceed high. (Note: Python handles arbitrary-precision integers automatically, so this overflow does not occur in Python).

Prevents 32-bit integer arithmetic overflow when low + high exceeds 2.14 billion.

Write a Python program for Binary Search implemented RECURSIVELY.

उत्तर एवं व्याख्या देखें

उत्तर:

def binary_search_recursive(lst, low, high, target):
    if low > high:
        return -1  # Base Case: Target absent
    mid = (low + high) // 2
    if lst[mid] == target:
        return mid
    elif target < lst[mid]:
        return binary_search_recursive(lst, low, mid - 1, target)
    else:
        return binary_search_recursive(lst, mid + 1, high, target)

nums = [10, 20, 30, 40, 50]
print(binary_search_recursive(nums, 0, len(nums) - 1, 30))  # Index 2

Base case low > high returns -1; recursive step calls function with adjusted low/high.

Compare the time and space complexity of iterative binary search versus recursive binary search.

उत्तर एवं व्याख्या देखें

उत्तर: • Time Complexity: Both iterative and recursive binary search have identical logarithmic time complexity $O(\log_2 n)$.
• Space Complexity: Iterative binary search uses $O(1)$ constant space (only 3 integer pointers). Recursive binary search uses $O(\log_2 n)$ auxiliary space on the call stack due to recursive stack frames.
Both are O(log n) time; iterative is O(1) space, recursive is O(log n) stack space.

अध्याय का अध्ययन पूर्ण हुआ?

अभ्यास के लिए तैयार?

ऑनलाइन CBT टेस्ट देकर तैयारी का मूल्यांकन करें

झारखण्ड बोर्ड परीक्षा पैटर्न पर आधारित बहुविकल्पीय प्रश्नों का ऑनलाइन टेस्ट दें। तुरंत परिणाम, समय विश्लेषण और प्रत्येक प्रश्न का विस्तृत हल प्राप्त करें।

फाउंडेशन टेस्ट

15 MCQs • मूल अवधारणाएँ

एडवांस्ड टेस्ट

15 MCQs • HOTS और ट्रैप्स