[Question]: Find SQRT of a number using binary search.
Example: Input: x = 8. Output: 2
// TC: O(lon(N))
// SC: O(1)
func findSQRT(_ n: Int) ->Int {
var low = 1
var high = n;
// Binary search on the answers:
while low <= high {
let mid = ((low + high) / 2)
let val = mid * mid
if (val <= n) {
// Eliminate the left half:
low = mid + 1
} else {
// Eliminate the right half:
high = mid - 1
}
}
return high
}
let inputSQRT = 16
let opSQRT = findSQRT(inputSQRT)
print("opSQRT is --- ", opSQRT) //opSQRT 4