'Sqrt(x)' Puzzle Walk-Through in C

Introduction

While there are a few ways to approach this problem, this guide will go over one of the most time-efficient methods--binary sort.

Follow along with me, and feel free to give the problem a try yourself!

Problem Statement

Return the non-negative square root of x rounded down to the nearest integer.

Process

Pseudocode approach to the problem.

int mySqrt(int x) 
{
	// Binary Search
	// The square root of x must be between 0 and x, our range
	// Start in the middle of the range
	// if square of mid > x, eliminate mid and the right half of range
	// if square of mid < x, eliminate mid and the left half of range
	// otherwise, if the square of mid == x, return mid
	// finally, if l > r, return r, the smaller of the two
}

Now, we can put code to our comments:

int mySqrt(int x) 
{
	// Binary Search
	// The square root of x must be between 0 and x, our range
	int l = 0;
	int r = x;
	int mid;

	// ensures
     while (l <= r)
     {
		// Start in the middle of the range
         mid = (l + r) / 2;
	
		// if square of mid > x, eliminate mid and right half of range
         if (mid * mid > x)
             r = mid - 1;
		// if square of mid < x, eliminate mid and left half of range
         else if (mid * mid < x)
             l = mid + 1;
		// if the square of mid == x, return mid
         else
             return mid;
     }
	
	 // finally, if l > r, return r, the smaller of the two
	 return r;
}

Another potential solution would be just starting from 0 and squaring each number, until the target is reached, but that algorithm would be slightly slower than Binary Search, with a time complexity of O ( sqrt n ).

In this way, we're cutting the problem in half each time the loop runs--O ( log n ).

Final Thoughts

Thanks for reading!