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