Anonymous user
Binary search: Difference between revisions
added invariants
(→{{header|Java}}: changed calculation of average - adding lo + hi, then dividing by two causes an overflow error with numbers close to Integer.MAX_VALUE) |
(added invariants) |
||
Line 24:
// initially called with low = 0, high = N-1
BinarySearch(A[0..N-1], value, low, high) {
// invariants: value > A[i] for all i < low
value < A[i] for all i > high
if (high < low)
return not_found // value would be inserted at index "low"
Line 40 ⟶ 42:
high = N - 1
while (low <= high) {
// invariants: value > A[i] for all i < low
value < A[i] for all i > high
mid = (low + high) / 2
if (A[mid] > value)
Line 57 ⟶ 61:
// initially called with low = 0, high = N - 1
BinarySearch_Left(A[0..N-1], value, low, high) {
// invariants: value > A[i] for all i < low
value <= A[i] for all i > high
if (high < low)
return low
Line 71 ⟶ 77:
high = N - 1
while (low <= high) {
// invariants: value > A[i] for all i < low
value <= A[i] for all i > high
mid = (low + high) / 2
if (A[mid] >= value)
Line 86 ⟶ 94:
// initially called with low = 0, high = N - 1
BinarySearch_Right(A[0..N-1], value, low, high) {
// invariants: value >= A[i] for all i < low
value < A[i] for all i > high
if (high < low)
return low
Line 100 ⟶ 110:
high = N - 1
while (low <= high) {
// invariants: value >= A[i] for all i < low
value < A[i] for all i > high
mid = (low + high) / 2
if (A[mid] > value)
| |||