Why isn't the time complexity logarithmic if its binary_search?

#1

Q2. Algorithms STL#2
Choose the correct output and time complexity for the following code :

list< int > myList = { 2, 6, 12, 13, 15, 18, 20};
cout << binary_search(myList.begin(), myList.end(), 20) ;

#2

@mehulbhandari358
Output is 1 and time complexity is Linear in size of the list.

#3

since it’s binary search why isn’t the time complexity logarithmic, that’s my question

#4

we are given list and list stl is very similar to the link list i.e we need to to traverse list from start to reach a particluar index.

if i represent recurrence relation for binary search on list then it will be something as ->

T(n)=T(n/2) + O(n) // O(n) because to reach to mid element we need to traverse half of the list which is equivalent to O(n) work.

On solving this recurrence relation we get O(n) time complexity