I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related (connected).
Now, at a certain point, there's a question:
How can you organize an edge list to make searching for a particular edge take O(lg E) time?
I was thinking to the trivial solution of sorting, but it is not so easy to sort a list of edges. For example, let the following be our initial list of edges:
[[3, 2], [1, 2], [1, 3]]
Now, if we try to sort it by using the first vertex, we obtain:
[[1, 3], [1, 2], [3, 2]]
I am not visualizing well if this search would be
O(lg E), where
E is the number of edges.
Could you please explain how could we organize the edges in order to have a edge searching algorithm with a time complexity of
O(lg E)? And why it should be