电商网站开发人员,网站建设定义是什么,网站建设优秀网,微信如何进入公众号二分查找(binary search)是一种基于分治策略的高效搜索算法。它利用数据的有序性#xff0c;每轮缩小一半搜索范围#xff0c;直至找到目标元素或搜索区间为空为止。
例#xff1a;给定一个n 的数组 nums #xff0c;元素按从小到大的顺序排列且不重复。请查找并返回元素 …二分查找(binary search)是一种基于分治策略的高效搜索算法。它利用数据的有序性每轮缩小一半搜索范围直至找到目标元素或搜索区间为空为止。
例给定一个n 的数组 nums 元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素则返回 −1 。示例如图所示。 如上图所示我们先初始化指针 i0 和 jn−1 分别指向数组首元素和尾元素代表搜索区间 [0,n−1] 。请注意中括号表示闭区间其包含边界值本身。
接下来循环执行以下两步。
计算中点索引 m ⌊(ij)/2⌋其中 ⌊⌋ 表示向下取整操作。判断 nums[m] 和 target 的大小关系分为以下三种情况。 当 nums[m] target 时说明 target 在区间 [m1,] 中因此执行 im1 。 当 nums[m] target 时说明 target 在区间 [i,m−1] 中因此执行 jm−1 。 当 nums[m] target 时说明找到 target 因此返回索引m 。
若数组不包含目标元素搜索区间最终会缩小为空。此时返回 −1 。 值得注意的是由于i 和 j 都是 int 类型因此 ij 可能会超出 int 类型的取值范围。为了避免大数越界我们通常采用公式 m⌊i(j−i)/2⌋ 来计算中点。
/* 二分查找双闭区间 */
int binarySearch(vectorint nums, int target) {// 初始化双闭区间 [0, n-1] 即 i, j 分别指向数组首元素、尾元素int i 0, j nums.size() - 1;// 循环当搜索区间为空时跳出当 i j 时为空while (i j) {int m i (j - i) / 2; // 计算中点索引 mif (nums[m] target) // 此情况说明 target 在区间 [m1, j] 中i m 1;else if (nums[m] target) // 此情况说明 target 在区间 [i, m-1] 中j m - 1;else // 找到目标元素返回其索引return m;}// 未找到目标元素返回 -1return -1;
}
时间复杂度为O(logn) 在二分循环中区间每轮缩小一半循环次数为。
空间复杂度为O(1) 指针 i 和 j 使用常数大小空间。
