Binary STL Quiz

#1

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) ;
Output is 20 and time complexity is Linear in size of the list.

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

Output is 20 and time complexity is Logarithmic in size of the list.

Output is 1 and time complexity is Logarithmic in size of the list.

According to me answer should be d but it is given b. Why so?

#2

Hey @adarsh_anand if the data structure is such that only sequential access is allowed meaning to access the nth element the time complexity is O(n) (like in linked list) the binary search Time complexity would be O(n). binary search has O(logn) time complexity only in data structures where time to access the nth element is O(1)
That is why the time complexity of binary search on arrays is O(logn) but on list is O(n)

1 Like
#3

Oh! Thanks. I got it.

1 Like