Member Search
|
|
Search
|
Watch Thread | My Post History | My Watches | User Settings View: Flat (newest first) | Threaded | Tree Previous Thread | Next Thread |
||
Forums
Tutorial Discussions
Binary Search tutorial
I need to add a small issue
|
||
| 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? |
|
|
Forums
Tutorial Discussions
Binary Search tutorial
I need to add a small issue
Previous Thread | Next Thread |
 |