Searching questions look easy until the examiner starts counting: exactly how many comparisons, on which array, and in the average or worst case? Binary-search traces on concrete arrays and comparison-count shortcuts are the recurring traps. Both patterns become predictable once you write the bounds or comparison tree.
GATE, ISRO, UGC NET, DSSSB, TPSC, BEL and Wipro papers repeatedly test search preconditions, midpoint traces and exact comparison counts. Sorting Algorithms: Comparison and Complexity places the same counting habit in the wider sorting context.
1. The 60-second toolkit before you attempt these
Keep these four results ready:
Linear search worst case: n comparisons.
Successful linear search average: (n + 1)/2 comparisons.
Binary search worst case on a sorted array: floor(log2 n) + 1 comparisons.
Finding both minimum and maximum by pairing: ceil(3n/2) - 2 comparisons.
For n = 10,00,000, 2^19 = 5,24,288 falls short, while 2^20 = 10,48,576 covers the array. Therefore, floor(log2 10,00,000) + 1 = 19 + 1 = 20 comparisons. Twenty "left or right?" questions settle a million sorted elements.
Binary search requires sorted input. Also, when a question asks for the minimum comparisons, look for pairing or a direct observation before running the obvious algorithm.
2. When can you even binary search? Preconditions and linear search behaviour
Q1. The necessary condition for using binary search in an array is:
(ISRO 2016, see the solved page)
(a) The array should not be too long
(b) The array should of more size
(c) The array should be sorted
(d) None of these
Answer: (c). Order tells binary search which half cannot contain the key. On unsorted data, that inference is invalid. Size affects the steps, not correctness. Binary-search traces require sorted input.
Q2. The average case occurs in Linear Search Algorithm when:
(UGC NET 2015, see the solved page)
(a) The item to be searched is in somewhere middle of the Array
(b) The item to be searched is not in the array
(c) The item to be searched is in the last of the array
(d) The item to be searched is either in the last or not in the array
Answer: (a). If the key is equally likely at every position, its expected position is around the middle. A last-position or absent key produces the worst case.
Q3. The average number of key comparisons done in a successful sequential search in a list of length n is
(TPSC 2025, see the solved page)
(a) log n
(b) (n - 1)/2
(c) n/2
(d) (n + 1)/2
Answer: (d). Position i costs i comparisons. The average is (1 + 2 + ... + n)/n = n(n + 1)/(2n) = (n + 1)/2. Option (c) drops the +1.
3. Trace it by hand: binary search on real arrays
Q4. Given an array X = (22, 33, 55, 88, 96) and key = 88. How many iterations are required to find the key using binary search?
(BEL 2023, see the solved page)
(a) 3
(b) 2
(c) 1
(d) 4
Answer: (b). Start with low = 0, high = 4. Mid = floor((0 + 4)/2) = 2 and X[2] = 55 < 88, so set low = 3. Next, mid = floor((3 + 4)/2) = 3 and X[3] = 88. That is two iterations, one per mid inspection.
Q5. Given an array arr = {45, 77, 89, 90, 94, 99, 100} and key = 99; what are the mid values (corresponding array elements) in the first and second levels of recursion?
(Wipro 2025, see the solved page)
(a) 90 and 99
(b) 90 and 94
(c) 89 and 99
(d) 89 and 94
Answer: (a). For indices 0 to 6, mid = floor((0 + 6)/2) = 3, so arr[3] = 90. Since 99 > 90, set low = 4, high = 6. Now mid = floor((4 + 6)/2) = 5, so arr[5] = 99. Recompute mid from the new bounds.
4. Counting comparisons: worst case and the honest average
Q6. Consider a sorted array of 10,00,000 elements. What is the maximum number of comparisons required to find the location of an item using binary search?
(DSSSB 2021, see the solved page)
(a) 20
(b) 6
(c) 21
(d) 7
Answer: (a). The maximum number of comparisons is floor(log2 10,00,000) + 1 = 19 + 1 = 20 because 2^20 = 10,48,576 first covers 10,00,000. For a quick estimate, 2^10 = 1,024 is about a thousand, so a million is about 2^20.
Q7. Suppose there are 11 items in sorted order in an array. How many searches are required on the average, if binary search is employed and all searches are successful in finding the item?
(ISRO 2014, see the solved page)
(a) 3.00
(b) 3.46
(c) 2.81
(d) 3.33
Answer: (a). The tree has 1 key at level 1, then 2, 4 and 4 at levels 2, 3 and 4. Total comparisons are 1(1) + 2(2) + 3(4) + 4(4) = 1 + 4 + 12 + 16 = 33. The average is 33/11 = 3.00, not a guess from log2 11.
5. From counting to complexity: the recurrence view
Q8. What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
(GATE 2021, see the solved page)
(a) Theta(sqrt n)
(b) Theta(log2 n)
(c) Theta(n^2)
(d) Theta(n)
Answer: (b). Each call does constant work and recurses on half the array, so T(n) = T(n/2) + Theta(1), which unrolls to Theta(log2 n). "Arithmetic operations" changes nothing because the work per call stays constant.
Q9. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is
(GATE 2008, see the solved page)
(a) Theta(n)
(b) Theta(log n)
(c) Theta(n*log n)
(d) Theta(1)
Answer: (b). A majority in a sorted array must occupy the middle position, so choose A[floor(n/2)]. Binary-search its first and last occurrence, then test last - first + 1 > n/2. Two binary searches cost Theta(log n). "Sorted" enables the method.
6. Clever counting: think before you run
Q10. Consider an unordered list of N distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?
(GATE 2025, see the solved page)
(a) 1
(b) N - 1
(c) N
(d) 2N - 1
Answer: (a). Compare any two elements. The smaller cannot be the list maximum, so one comparison gives a valid answer. Zero comparisons cannot guarantee that. The trap is solving the harder second-largest problem.
Q11. An array of n numbers is given, where n is an even number. The maximum as well as the minimum of these n numbers needs to be determined. Which of the following is TRUE about the number of comparisons needed?
(GATE 2007, see the solved page)
(a) At least 2n - c comparisons, for some constant c, are needed.
(b) At most 1.5n - 2 comparisons are needed.
(c) At least n log2 n comparisons are needed.
(d) None of the above.
Answer: (b). Compare n/2 pairs, costing n/2 comparisons. Find the maximum among pair-winners in n/2 - 1 comparisons and the minimum among pair-losers in another n/2 - 1. Total: n/2 + (n/2 - 1) + (n/2 - 1) = 3n/2 - 2. A two-pass scan costs 2n - 3.
Q12. (NAT) The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _____.
(GATE 2014, see the solved page)
Answer: 148. Apply Q11: 3(100)/2 - 2 = 150 - 2 = 148. That is 50 pair comparisons, 49 among the winners and 49 among the losers: 50 + 49 + 49 = 148. GATE tested the theory in 2007 and the numerical form in 2014, so solve PYQs in families.
7. Score yourself and what to drill next
At 10 to 12, move to sorting and recurrences. At 7 to 9, redo Q6, Q7, Q11 and Q12 because counting is the likely weak point. Below 7, rebuild linear and binary search from Q1 to Q3.
For more solved sets, continue with Algorithms MCQs. The GATE CS exam preparation collection places searching alongside the wider syllabus.
Use the GATE Test Series for topic-wise algorithm tests and full mocks under time pressure. If you need the ideas in sequence, Zero to Hero teaches searching and sorting through structured lectures.
Use each solved page to check the trace. Use them as a revision loop: attempt, check the trace, and repeat until comparison counts stop feeling like guesses.
