Interesting Application of Binary Searching


What is done?

In, normal binary search we search for first/suitable occurence of the correct answer. Here also we do something similar.


You are to form an MST such that the no. of edges in the MST that are connected to the index 1 is k which is given.

EdgesMST connected to 1 = kEdges \in MST\ connected\ to\ 1\ =\ k


We introduce the following idea - to prioritize the edges connected to 1 we add a separate suitable

weight to the edges that have the node 1 in them (during the formation of the MST).

Now we binary search over the suitable weight.