JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
I need to add a small issue | Reply
In some cases, I would like to know what is the first possible position to insert a new element in the array keeping it sorted:
(The index which it will take after inserting it)

binary_search(lo, hi, p):
while lo < hi:
mid = lo + (hi-lo)/2
if p(mid) == true:
hi = mid
else:
lo = mid+1

return lo // lo is the least x for which p(x) is true

here p() will return true if the mid element is >= current element.

This is the same as the first pseudocode under the section:
Implementing the discrete algorithm, with two differences:
1) hi will be array_length+1 because the search space will contain an additional index at last (lo will be 1 as it is)
2) Remove the line if p(lo) == false: complain
This may also help to make a faster check (if we need to know that this element is at last index - which is (length+1)): "if lo==length+1" instead of "if p(lo) == false" which may be not efficient if p() takes long time.

Is there anything wrong with this psudocode?
RSS