Consider: Identify the type of searching performed in the above code.
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Consider:**
int search(int arr[], int l, int r, int item)
{
if(r<l)
return(-1);
if(arr[l] == item)
return(l);
if(arr[l] == item)
return(l);
return(search(arr, l+1, r));
}
Identify the type of searching performed in the above code.
Show answer & explanation
The function performs linear search by sequentially checking elements from index l onwards (incrementing by 1 via l+1), comparing each element with the target item. It returns the index when found or -1 if the search space is exhausted. Binary search would use division (mid-point), exponential search would use exponential jumps, and Fibonacci search uses Fibonacci numbers for partitioning—none of which occur here.
Step-by-step Derivation:
Analysis of the recursive function:
- Base case: if
r < l, search space is exhausted, return -1 - Comparison: checks if
arr[l] == item(redundant check appears twice) - Recursion: calls
search(arr, l+1, r)— increments left pointer by 1 - Pattern: The left pointer advances by exactly 1 position per recursive call, checking each element sequentially from left to right
- Conclusion: This is the hallmark of linear search—sequential traversal checking one element at a time
Note: The code contains a logic error (duplicate condition), but the search strategy is unmistakably linear based on the l+1 increment pattern.