Introduction
Searching means finding whether (and where) a given value — the key — exists inside a collection of data. Divide-and-conquer (D&C) is a general problem-solving strategy that breaks a big problem into smaller problems of the same kind, solves each, and combines the answers. These two topics are joined together because the single most famous searching algorithm — binary search — is the cleanest example of divide-and-conquer, and the same recursion mathematics (recurrences, the Master Theorem, O(log n) and O(n log n) behaviour) reappears everywhere in the subject.
For BCS, Bank IT, and IT-officer exams this is a guaranteed scoring area: examiners love asking the number of comparisons in binary search, the time complexity of merge sort, "which requires a sorted array", tracing a search, and applying the Master Theorem. Master this lesson and you can answer almost any MCQ or short question on it.
Learning objectives
- Define searching and distinguish linear (sequential) search from binary search.
- Derive the time complexity of linear and binary search and know their best/worst/average cases.
- State the three steps of the divide-and-conquer paradigm and recognise D&C algorithms.
- Write and trace binary search (iterative and recursive) and count comparisons.
- Set up recurrence relations and solve them with the recursion tree and the Master Theorem.
- Understand merge sort as the model D&C algorithm and know its Θ(n log n) cost.
- Avoid the classic exam traps (unsorted arrays, off-by-one bounds, overflow in mid).