[Leetcode]0069二分法

// lc0069.cpp 二分法
// C语言中long和int是一样的，long long才是真正的64bit
// 32bit最大int 是2147483647 或者0x7FFFFFFF

#include "stdafx.h"
#include <stdio.h>

int guess(long long x, long long y){
   if((x*x) <= y)
      return 1;
   else
      return 0;
}

int mysqrt(int y){
   long long L=0,R=(long long)y+1;//[0,y)
   long long ans=0;
   long long mid;
   while(L<R){
      mid=(L+R)/2;
      if(guess(mid,y)){
         ans=mid;
         L=mid+1;
      }else{
         R=mid;
      }
   }
   return (int)ans;
}
int main(int argc, char* argv[])
{
   int T,i,y,result;
   freopen("lc0069i.txt","r",stdin);
   scanf("%d",&T);
   for(i=0;i<T;i++){
      scanf("%d",&y);
      result=mysqrt(y);
      printf("Result is %d\n", result);
   }
   return 0;
}
/*
5
361
10000
16
2147395599
2147483647
*/

// lc0069.cpp 这里一定要注意的是
// C语言中long和int是一样的，long long才是真正的64bit
// 32bit最大int 是2147483647 或者0x7FFFFFFF

#include "stdafx.h"
#include <stdio.h>
#include <time.h>
#include <windows.h>

int guess(long long y, long long x){
   if((y*y) <= x)
      return 1;
   else
      return 0;
}

int mysqrt01(int x){
   long long L=0,R=(long long)x+1;//[0,x)
   long long ans=0;
   long long mid;
   while(L<R){
      mid=(L+R)/2;
      if(guess(mid,x)){
         ans=mid;
         L=mid+1;
      }else{
         R=mid;
      }
   }
   return (int)ans;
}

int mysqrt02(int x)
{
   int L,R,mid;
   if (x == 0)
      return 0;
   L=1;
   R=x;
   while(1){
      mid = L + (R - L)/2;
      if (mid > x/mid) {
            R = mid - 1;
        } else {
            if (mid + 1 > x/(mid + 1))
                return mid;
            L = mid + 1;
        }
    }
}


/*
The sequence 1, 2, ... , n has no duplication.
Near the very end, closest step, before while loop, left = mid = right.
In while, If mid < sqrt(x), left = mid + 1 executed, right pointer
   is not moving, and right is the answer.
In while, If mid > sqrt(x), right = mid - 1 executed, right pointer shifts left 1,
   closest to sqrt(x), right is also the answer.
*/
int mysqrt03(int x)
{
   int L=1;
   int R=x;
   int mid;
   while(L<=R){
      mid=L+(R-L)/2;
      if(mid==x/mid){
         return mid;
      }else if(mid < x/mid){
         L=mid+1;
      }else{
         R=mid-1;
      }
   }
   return R;
}

int main(int argc, char* argv[])
{
   int T,i,x,result,t;
   freopen("lc0069i.txt","r",stdin);
   scanf("%d",&T);
   t=GetTickCount();
   for(i=0;i<T;i++){
      scanf("%d",&x);
      result=mysqrt03(x);
      printf("Result is %d\n", result);
   }
   t=GetTickCount()-t;
   printf("Time cost %d\n",t);
   return 0;
}
/*
5
361
10000
16
2147395599
2147483647
*/