Binary Search First Occurrence

object Main {
	def main(args: Array[String]): Unit = {
		val arr = Array(1, 2, 4, 4, 4, 7, 9)
		val target = 4
		var lo = 0
		var hi = arr.length - 1
		var result = -1
		while (lo <= hi) {
			val mid = lo + (hi - lo) / 2
			if (arr(mid) == target) {
				result = mid
				hi = mid - 1
			} else if (arr(mid) < target) {
				lo = mid + 1
			} else {
				hi = mid - 1
			}
		}
		println(result)
	}
}