binary search notes

Binary Search

// target
// a (a sorted array)

var lo = 0        // inclusive bound
var hi = a.length

while (lo < hi) {
  val mid = (lo+hi)/2  // lo+(hi-lo)/2  (this version may be better)

  if(a(mid)==target) return true
  else if(a(mid) < target) lo = mid
  else hi = mid
}

=====

def isqrt(n: Int): Int = {
  var lo = 0
  var hi = n/2

  while (lo < hi) {
    val mid = (hi-lo)/2
    val check = mid*mid

    if(check == n) mid
    else if(check < n) hi = mid-1
    else lo = mid
  }
}

// that doesn't work though

def isqrt(n: Int): Int = {
  var lo = 0
  var hi = n  // inclusive
  while() {
    val mid = (lo+hi+1)/2

    if(mid*mid <= n) lo = mid
    else hi = mid-1
  }
  lo
}