// Invariant: x[i-1] < target, x[j] >= target.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if cmp.Less(x[h], target) {
			i = h + 1 // preserves x[i-1] < target
		} else {
			j = h // preserves x[j] >= target
		}
	}
	// i == j, x[i-1] < target, and x[j] (= x[i]) >= target  =>  answer is i.

}

func heapSiftUp(heap []*batchCursor, i int) int {
	for i > 0 && heap[(i-1)/2].ev.time > heap[i].ev.time {
		heap[(i-1)/2], heap[i] = heap[i], heap[(i-1)/2]
		i = (i - 1) / 2
	}
	return i
}

func heapSiftDown(heap []*batchCursor, i int) int {
	for {
		m := min3(heap, i, 2*i+1, 2*i+2)
		if m == i {
			// Heap invariant already applies.
			break
		}
		heap[i], heap[m] = heap[m], heap[i]
		i = m
	}

}

func (i Instances) NamespacedName() NamespacedName {
	return i.Config().NamespacedName()
}

func (i Instances) PortForName(name string) Port {
	return i.Config().Ports.MustForName(name)
}

func (i Instances) Config() Config {
	return i.mustGetFirst().Config()
}

func (i Instances) Instances() Instances {
	return i
}

func (i Instances) mustGetFirst() Instance {

		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

// Find uses binary search to find and return the smallest index i in [0, n)
// at which cmp(i) <= 0. If there is no such index i, Find returns i = n.
// The found result is true if i < n and cmp(i) == 0.

// but less expensive than, calling [Remove](h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // parent
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

func down(h Interface, i0, n int) bool {

	f *File
}

func (i fileInfo) Name() string       { return path.Base(i.f.Name) }
func (i fileInfo) ModTime() time.Time { return i.f.Time }
func (i fileInfo) Mode() fs.FileMode  { return i.f.Mode }
func (i fileInfo) IsDir() bool        { return i.f.Mode&fs.ModeDir != 0 }
func (i fileInfo) Size() int64        { return i.f.Size }
func (i fileInfo) Sys() any           { return nil }

func (i fileInfo) String() string {

			return i
		}
		i++
		fails++
		if fails >= 4+i>>4 && i < t {
			// See comment in ../bytes/bytes.go.
			j := bytealg.IndexRabinKarp(s[i:], substr)
			if j < 0 {
				return -1
			}
			return i + j
		}
	}
	return -1
}

func Cut(s, sep string) (before, after string, found bool) {
	if i := Index(s, sep); i >= 0 {
		return s[:i], s[i+len(sep):], true
	}
	return s, "", false
}

		sum := 0
		for i := 0; i < 1000; i++ {
			sum += i
		}
		fmt.Println("Computed once:", sum)
		return sum
	})
	done := make(chan bool)
	for i := 0; i < 10; i++ {
		go func() {
			const want = 499500
			got := once()
			if got != want {
				fmt.Println("want", want, "got", got)
			}
			done <- true
		}()
	}
	for i := 0; i < 10; i++ {
		<-done
	}
	// Output:

		m := map[interface{}]int{}
		for i := 0; i < n; i++ {
			m[i] = 1
		}
	})

	// ~7ms on a 1.6GHz Zeon.
	// Regression test for CL 119360043.
	checkLinear("iface", 10000, func(n int) {
		m := map[I]int{}
		for i := 0; i < n; i++ {
			m[C(i)] = 1
		}
	})

	// ~6ms on a 1.6GHz Zeon.
	checkLinear("int", 10000, func(n int) {
		m := map[int]int{}
		for i := 0; i < n; i++ {
			m[i] = 1
		}
	})

	v := BatchJobExpire{}
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		v.MarshalMsg(nil)
	}
}

func BenchmarkAppendMsgBatchJobExpire(b *testing.B) {
	v := BatchJobExpire{}
	bts := make([]byte, 0, v.Msgsize())
	bts, _ = v.MarshalMsg(bts[0:0])
	b.SetBytes(int64(len(bts)))
	b.ReportAllocs()
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		bts, _ = v.MarshalMsg(bts[0:0])
	}
}