传媒公司制作网站,传媒公司名字大气一些,咨询公司来公司做调查,网站推广怎么做关键词一、题目 函数原型#xff1a;int mySqrt(int x) 二、思路 利用二分查找思想#xff0c;在0与x区间进行查找。 设置左边界 left #xff08;初始值为0#xff09;#xff0c;右边界 right#xff08;初始值为x#xff09;和中值 mid #xff08;值为区间的中间值#… 一、题目 函数原型int mySqrt(int x) 二、思路 利用二分查找思想在0与x区间进行查找。 设置左边界 left 初始值为0右边界 right初始值为x和中值 mid 值为区间的中间值同时设置一个ans初始值为-1作为最终返回值。 设置循环循环条件为 leftright。每次进入循环通过中值mid的平方与x进行比较确定x的平方根在中值左区间还是右区间或是mid即为x的平方根。mid平方小于x则说明平方根在中值左区间大于x则说明平方根在中值右区间。 每次进入循环先更新一下mid的值然后再进行比较判断确定平方根所在区间。将平方根在左区间和平方根刚好等于mid的情况合并。如果平方根在左区间或平方根刚好等于mid则更新区间并将mid的值赋值给ans如果平方根在右区间则只更新区间。 最终循环结束后返回ans。 关键1中值mid值如何求 mid left right - left/ 2 关键2为什么循环条件是 leftright 只有当left right 时才能保证要求的平方根在区间内。left right 时也算一个区间只不过该区间只有一个值。 关键3为什么只有当mid的平方小于等于x时才将mid的值赋给ans 当mid的平方等于x时将mid的值赋给ans毋庸置疑。当mid的平方小于x时将mid的值赋给ans是因为在循环中可能会出现所求平方根的精确值在两个相邻整数之间此时mid的值时较小的整数我们要求的粗略值也是较小的整数因此mid的值就是我们要求的ans值。 关键4为什么mid的平方需要强制类型转换 因为题目提示部分显示x2^31-1数据较大int类型可能能存放不下需要用long long类型存储。 int mySqrt(int x)
{int left 0;int right x;int mid left (right - left) / 2;int ans -1;while (left right){mid left (right - left) / 2;if ((long long)mid * mid x ){left mid 1;ans mid;}else if ((long long)mid * mid x ){right mid - 1;}}return ans;
}
