Finding Sqrt of a number using Binary Search

[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

Leave a Comment

Your email address will not be published. Required fields are marked *