Linear search examines successive entries until a match or a stopping condition is reached; in the worst case it inspects entries. Binary search uses a sorted array to discard about half of the remaining candidates after each comparison, requiring comparisons. Its logarithmic guarantee also requires constant-cost indexed access, as supplied by an array; the same index operations on a linked list would not be constant-cost.
Return the lower-bound search boundary, permitting both zero and the array length:The precondition includes nondecreasing order. The loop invariant isInitially both excluded ranges are empty. If , sortedness justifies excluding every position through
def lowerBound(a: Array[Int], x: Int): Int = {
require(a != null) // a is nondecreasing
var lo = 0
var hi = a.length
while (lo < hi) {
val mid = lo + (hi - lo) / 2
if (a(mid) < x) lo = mid + 1
else hi = mid
}
lo
}mid; otherwise it justifies excluding every position from mid onwards. The loop variant is a nonnegative integer that strictly decreases. When the old width is positive, mid is a valid array index. The midpoint expression avoids adding two potentially large indices. At exit , so lo satisfies the required partition, including when . Each new width is at most half the old width, rounded down; this gives time complexity and constant space, conventionally for nontrivial sizes.A second binary search locates the first entry strictly greater than For upper-bound search, the loop invariant is , , and ; its loop variant is again . The same midpoint and sortedness arguments prove preservation, termination and time complexity. The first binary search in part (b) already has its own loop invariant and loop variant.
x:def upperBound(a: Array[Int], x: Int): Int = {
require(a != null) // a is nondecreasing
var lo = 0
var hi = a.length
while (lo < hi) {
val mid = lo + (hi - lo) / 2
if (a(mid) <= x) lo = mid + 1
else hi = mid
}
lo
}
def equalRange(a: Array[Int], x: Int): (Int, Int) =
(lowerBound(a, x), upperBound(a, x))Let the two boundaries be . There cannot be a value greater than before the first value at least , so . Every entry between them is simultaneously at least and at most , hence equals . Entries before are smaller and entries at or after are larger, so the interval cannot be extended at either end. This proves the equal-range search result is maximal. If
x is absent, i == j, both equal to its insertion position; this can be zero, , or an interior gap. Two logarithmic searches still have logarithmic total time complexity. Computing an upper boundary as lowerBound(a, x+1) would introduce an unnecessary integer overflow bug at the largest integer.Black-box testing chooses inputs and expected outputs from the public specification without using the implementation's control structure. Equivalence class testing partitions the input space into classes expected to exercise similar specified behavior, then chooses representatives; boundary cases test where that behavior changes. For equal-range search, use these concrete representatives:
- Empty array:
([], 4)gives(0,0). - One entry, with the target below, equal, and above it:
([4],3),([4],4),([4],5)give(0,0),(0,1),(1,1). - An absent interior value:
([1,3,5],4)gives(2,2). - One interior match:
([1,3,5],3)gives(1,2). - A repeated interior block:
([1,3,3,3,5],3)gives(1,4). - A repeated block touching the left or right boundary:
([3,3,5],3)and([1,3,3],3)give(0,2)and(1,3). - Every entry equal:
([3,3,3],3)gives(0,3); targets two and four give(0,0)and(3,3). - Extreme keys:
([Int.MinValue,0,Int.MaxValue],Int.MaxValue)gives(2,3), and searching forInt.MinValuegives(0,1).
For each result independently check , the strict inequalities outside the returned interval, and equality inside it. Unsorted inputs violate the precondition; they are not ordinary members of the specified valid-input classes. Software testing supplies evidence about implementations, while the loop invariant proof explains correctness for every valid input.
Articles by others on the same topic
There are currently no matching articles.