Binary Search

[Google] Binary Search related problem:

      Given an sorted array = {1.2, 7.5, 9.3, 10.2 } and  number x = 8.2, please find a closest element from the array.

Solution:

For the generic binary search framework template:

       int binarysearch( vector<int> &nums, int x)

       { 

           int start = -1;

           int end = nums.size();

           int mid;

           while(end - start > 1) {

             mid = (start + end )/2;

             if (nums[mid] > x) {

                 end = mid;  

             } 

             else {

                 start = mid;

             }

        }

Let's see how this problem fits into the framework.

[Code]
float Solution(vector <float> &nums, float x)
{
     int start = -1;
     int end  = nums.size();
     int mid;
     while(end - start > 1) {
         mid = (end + start)/2;
         if ( nums[mid] > x ) {
             end = mid;
         }
         else {
            start = mid;
         }
     }
     return (x - nums[start]) > (nums[end] -x) ? nums[end]: nums[start];
}




Square Root of X

Implement float sqrt (float x). Compute and return the square root of x.

here x > 1




Solution:

[Code]
float FindSqrt(float x)
{
     float start = -1;
     float end = x;
     float mid;
     while(end - start > 0.01) {
        mid = (end + start) /2;
           if( mid *mid  > x)
               end = mid;
           else start = mid;
     }
     return mid;
}