I am working on a problem where I need to binary search on a given array and there can be updates for a given index. As the updates can occur frequently, I need to do it as efficiently as possible. Could you please suggest an appropriate data structure which would update the element in O(log n) and allow me to perform binary search on the array as well? The constant time update (updating by index) won't work as after each update, I have to sort the elements again in order to be able to perform binary search on it later, which would take the complexity to O(nlogn) for each update.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
If you use any balanced binary search tree data structure, each read and update can be done in $O(\log n)$ time. Binary search can also be done in $O(\log n)$ time -- it is just a read (search) operation in the tree.
