Maintain the required boundary between entries strictly above the target and entries at most the target:The full invariant is , every entry before is greater than , and every entry at or after is at most . The array remains unchanged. Descending order justifies each update: if the middle value is greater, all earlier values are greater too; otherwise all values from the middle onward are at most the target.
def search(u: Array[Int], z: Int): Boolean = {
var a = 0
var b = u.length
while (a < b) {
val middle = a + (b - a) / 2
if (u(middle) > z) a = middle + 1
else b = middle
}
a < u.length && u(a) == z
}The nonnegative loop variant strictly decreases, with each update retaining at most half the old candidate length. On termination , which is the first index whose value could be at most . Equality at that index is therefore necessary and sufficient for presence. Short-circuit evaluation makes the final test safe when , including the empty-array case. The time is , using constant auxiliary space.
Return immediately on equality and omit the final array inspection:An equality returns a genuine matching entry. After a nonequal comparison, descending order excludes the inspected middle entry and one whole side. In the half-open range, setting
def searchEarly(u: Array[Int], z: Int): Boolean = {
var a = 0
var b = u.length
while (a < b) {
val middle = a + (b - a) / 2
val value = u(middle)
if (value == z) return true
if (value > z) a = middle + 1
else b = middle
}
false
}b = middle already excludes the middle index; subtracting one would incorrectly exclude another possible entry. The candidate interval decreases as before, so absence is reported exactly when no possible entry remains.For an array of size , the first probe finds the uniformly selected target with probability . Otherwise it leaves a half of size ; conditional on entering that half, its target is uniform there. Counting the first iteration in every case givesFor , the successful-search decision tree has targets at depth , requiring iterations. ThusThe numerator is , as follows by induction or by shifting and subtracting a finite geometric sum. Substituting givesThe base gives one iteration, as required.
The expected number is exactly . In the boundary-search version, an interval of length is reduced to length whichever comparison branch is taken. It must therefore take exactly iterations to reduce length to zero, including when a probe has already equaled the target. The result holds for every target in this case, so averaging does not change it.
The expected saving on the specified successful searches iswhich tends to one iteration as increases. The fractional saving is , which tends to zero. Both versions have logarithmic expected time, and the improvement is a bounded average saving rather than a change of growth rate. A target at the first middle position benefits greatly, but the uniform distribution does not concentrate on that event. The extra equality branch and machine-level costs also matter when comparing measured execution times.
Articles by others on the same topic
There are currently no matching articles.