||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
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?