This question was asked in our exam long a go and I don't remember exact words.

The scenario was, Initially you are given a set of finite data to start with, and a key value (which you have to find in a given set). Can we terminate binary search algorithm/program, if we grow the size of the data by feeding new finite data in different quantum during the search is going on.

e.g. if I am searching name of a person in a directory, and there is a on-going survey of the new connections by telecom dept., which they are transmitting in database from remote location continuously (without interruption) and those newly found data are fed in binary-search in real time.

Can we say that binary search will terminate for the key value in this scenario before new data is fed?, if yes then how to prove it?

Sorry, if I am not clear enough. I will try to explain further if required.

  • 2
    $\begingroup$ The setting is not clear. For example, generally speaking, we can postpone all insertions when a search takes place, and postpone all searches when an insertions takes place. It is unclear whether this would be a satisfactory answer, and if not, why exactly it won't. $\endgroup$ – Gassa Jul 18 '18 at 13:35
  • 3
    $\begingroup$ The question form here could be "design a data structure such that ...". If so, the "such that what exactly?" question has to be answered. For example, we can ask whether a single search and a single insertion can both take $O(\log n)$ time (yes with a binary search tree). If it is the point to additionally allow multiple concurrent calls to both functions, some additional formal criteria have to be established. $\endgroup$ – Gassa Jul 18 '18 at 13:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.