Binary Search 최종 버전

Go언어의 Binary Search 구현 이 아주 깔끔해서 앞으로 계속 사용하기로 했다.

Go

func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// 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
}

Parameter

Return

f(i) == true를 만족하는 가장 작은 i 값.

n을 반환할 수 있다.

-1은 반환되지 않는다.

Typescript (약간 수정)

function search(n: number, f: (x: int) => boolean, i = 0) {
  let j = n

  while (i < j) {
    const h = (i+j) >> 1
    if (!f(h)) {
      i = h + 1
    } else {
      j = h
    }
  }

  return i
}

Typescript 문법으로 i의 범위를 지정할 수 있다. 성능에 큰 차이는 없지만 기분이 더 좋아지는 효과가 있다.