Leetcode: sqrt(int x) with detailed description (C++)

PROBLEM:

Implement int sqrt(int x).

Compute and return the square root of x.

Hide Tags

 Math Binary Search

Hide Similar Problems

 (M) Pow(x, n)

KEYS:
1. A good example to practice binary search. A BS method can be shown as following figure:

2. Before applying this method, we need to identify the BOUNDERS: the min and max bounder. Then compare the mid value to decide which half should be used in the next round. And the middle value often is set as (min+max)/2.

3. The end condition. The searching loop should be ended when result is found or only two items left in the list.




//////////////////////////////////////////////////////////////////////////////
//codes in c++

class Solution {

public:

       int mySqrt(int x) {

              int i_max = x / 2 + 1;

              int i_mid = (i_max) / 2;

              int i_low = 0;

              int s_tmp;

              if (x<0)return -1;

              if (x == 0) return 0;

              while (1){

                     s_tmp = i_mid*i_mid;

                     //

                     if (i_mid + 1 == i_max) {

                           return abs(s_tmp-x)<abs(i_max*i_max-x) ? i_mid : i_max;

                     }

                     if (s_tmp>x){

                           i_max = i_mid;

                     }

                     else if (s_tmp<x){

                           i_low = i_mid;

                     }

                     else{

                           return i_mid;

                           break;

                     }

                     i_mid = (i_max+i_low) / 2;

                     if (i_low == i_max){

                           return i_low;

                           break;

                     }

              }

       }

};