Binary_search() Question Doubt

#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) ;

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

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

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

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

#2

@Kinjal
whats your doubt?
Its answer is b, because for linked list has the property that the only way you can find a particular node is to start at one end of the list and follow the links from one node to the next, checking them one at a time. Unlike with array subscripting, there is no way to compute the location of a list node directly from its numerical position in the list — because it could be anywhere in memory.

I hope this was your doubt.
If it is clear now then please mark the doubt as resolved otherwise if you have some query then you can ask.

#3

When I see that it’s calling binary_search, so I picked option d.

#4

I have forgot the thing that it uses list STL. So, always in any operation in list STL, take O(n) time. Got it.

1 Like
#5

okay, i hope you also understand the exact logic, why it is O(N).
because the nodes for list are not present in contiguous memory locations.
now you can mark this doubt as resolved.

#6

yes, all the nodes in the heap memory are connected by linker(self referential pointer). I guess.

1 Like