How can time complexity in Q2 be linear?

#1

how can the time complexity in the Q2 is linear.Should it not be logarithmic as the search is binary

#2

@TusHar-AroRa-2294450460870717
Hello Tushar,
list stl is linked list ,so to find mid element of list we need to traverse half of the list everytime.
we can write recurrence relation for binary search as.
T(n)=T(n/2) + O(n) // O(n) to traverse half of list to find mid

on solving this recurrence relation we get time complexity as O(n) and not O(logn)