废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【二分查找】，使用【数组】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。
m明确标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。
X的平方根【EASY】
一道可以模拟为二分方式做的题
题干
解题思路
由于 x 平方根的整数部分 ans 是满足 k*k≤x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案，。从题目的要求和示例我们可以看出，这其实是一个查找整数的问题，并且这个整数是有范围的。
- 如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
- 如果这个整数的平方 严格大于 输入整数，那么这个整数肯定不是我们要找的那个数；
- 如果这个整数的平方 严格小于 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
因此我们可以使用「二分查找」来查找这个整数，不断缩小范围去猜。
- 猜的数平方以后大了就往小了猜；
- 猜的数平方以后恰恰好等于输入的数就找到了；
- 猜的数平方以后小了，可能猜的数就是，也可能不是。
二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。由于我们所有的运算都是整数运算，不会存在误差，因此在得到最终的答案 ans后，也就不需要再去尝试 ans+1了
代码实现
给出代码实现基本档案
基本数据结构：整数
辅助数据结构：无
算法：二分查找
技巧：无
其中数据结构、算法和技巧分别来自：
- 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
- 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
- 技巧：双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*; class Solution { public int mySqrt(int x) { // 1 定义左右指针和取整的上界 int left = 0; int right = x; int ans = -1; // 2 进行常规的二分查找 while (left <= right) { int mid = left + (right - left) / 2; long curValue = (long)mid * mid; if (curValue > x) { // 当前值大于目标值，例如x为9，curValue为4，此时缩小右边界 right = mid - 1; } else if (curValue < x) { // 即使当前值并非目标值，但因为要啊向下取整，所以暂时赋值给ans，例如目标值3，当前值1 ans = mid; left = mid + 1; } else if (curValue == x) { // 当前值刚好为目标值，返回其平方根，例如：1 return mid; } } // 3 未在循环里找到准确平方根，则向下取整 return ans; } }
复杂度分析
时间复杂度：O(log n)，二分法最坏情况对n取2的对数
空间复杂度：O(1)，常数级变量，无额外辅助空间
