二分查找

定义：

• 二分查找（binary search）是一种基于分治策略的高效搜索算法。
• 它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

具体操作：

1. 先初始化指针 $i = 0$ 和 $j = n - 1$ ，分别指向数组首元素和尾元素，代表搜索区间 $[0, n - 1]$
2. 计算中点索引 $m = \lfloor {(i + j) / 2} \rfloor$ （其中 $\lfloor \: \rfloor$ 表示向下取整操作）
3. 判断 nums[m] 和 target 的大小关系，分为以下三种情况：
   1. 当 nums[m] < target 时，说明 target 在区间 $[m + 1, j]$ 中，因此执行 $i = m + 1$ 。
   2. 当 nums[m] > target 时，说明 target 在区间 $[i, m - 1]$ 中，因此执行 $j = m - 1$ 。
   3. 当 nums[m] = target 时，说明找到 target ，因此返回索引 $m$ 。
4. 重复2、3步骤，一直未找到元素，则搜索区间缩小为空。此时返回 $-1$ 。
5. 注意项：由于 $i$ 和 $j$ 都是 int 类型，因此 $i + j$ 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式 $m = \lfloor {i + (j - i) / 2} \rfloor$ 来计算中点