current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 0 down vote favorite

A is a sorted list. B is a sorted list, and a subset of A.

If an element is inserted into A at index i what's the most efficient way to determine the correct index i' for it's position in B?

Given the fact that both lists are sorted, and that we know B is subset of A I would think we should be able to devise quite an efficient algorithm, but I'm not happy with what I've come up with so far.

Thanks!

share|improve this question
    
I think the being a subset is of little value if you have no guarantee that B is a congruent part of A; in other words that the distances between common elements are equal. Doing a binary search on both seems plenty efficient to me with the additional advantage of simplicity. –  Thijs van Dien Apr 6 at 10:24
    
I would recommend giving us some context for the exact problem your trying to solve as opposed to only the abstracted form. This is most definitely one of those problems that have numerous ways it could be approached so having more specific details will likely yield better answers. –  Kenneth Apr 7 at 0:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.