//
// Created by Mr.Hu on 2018/6/25.
//
// leetcode 69 sqrt x
//
// 题目要求求x的平方根,如果非整数,则只返回其整数部分
//
// 这个题目就相等于搜索一个自然数数列,即符合二分查找的要求:有序且非重复
//
// 采用binary search的方法,循环终止条件为left>right,初始化left=0,right=x/2,
// 如果存在数mid的平方等于x,则return mid;否则一直循环,直到left>right,循环结束。
// 我们可以分析一下,在left>right之前,left==right,而此时mid也和它们相等,要么midmid>x,此时right-=1;
// 要么midmid<x,此时left+=1,所以最终的结果都是leftleft>x并且rightright<x,因此最终的结果就是right的值,
// 或者说是left-1
//
// 但是有一个特殊情况,x=1时,我们需要单独判断。
//
1 |
|