当前位置：首页 > news >正文

扁平风格网站模板百度竞价点击一次多少钱

news 2025/11/6 0:28:08

扁平风格网站模板,百度竞价点击一次多少钱,网站程序开发技术,秦皇岛网站制作报价一、是什么在计算机科学中，二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法想要应用二分查找法，则这一堆数应有如下特性： 存储在数组中有序排序搜索过程从数组的中间元素开始&…

一、是什么

在计算机科学中，二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法

想要应用二分查找法，则这一堆数应有如下特性：

存储在数组中
有序排序

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束

如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较，如果在某一步骤数组为空，则代表找不到，这种搜索算法每一次比较都使搜索范围缩小一半。

相比普通的顺序查找，除了数据量很少的情况下，二分查找会比顺序查找更快。

二、如何实现

基于二分查找的实现，如果数据是有序的，并且不存在重复项，实现代码如下：

function BinarySearch(arr, target) {if (arr.length <= 1) return -1// 低位下标let lowIndex = 0// 高位下标let highIndex = arr.length - 1while (lowIndex <= highIndex) {// 中间下标const midIndex = Math.floor((lowIndex + highIndex) / 2)if (target < arr[midIndex]) {highIndex = midIndex - 1} else if (target > arr[midIndex]) {lowIndex = midIndex + 1} else {// target === arr[midIndex]return midIndex}}return -1
}

如果数组中存在重复项，而我们需要找出第一个制定的值，实现则如下：

function BinarySearchFirst(arr, target) {if (arr.length <= 1) return -1// 低位下标let lowIndex = 0// 高位下标let highIndex = arr.length - 1while (lowIndex <= highIndex) {// 中间下标const midIndex = Math.floor((lowIndex + highIndex) / 2)if (target < arr[midIndex]) {highIndex = midIndex - 1} else if (target > arr[midIndex]) {lowIndex = midIndex + 1} else {// 当 target 与 arr[midIndex] 相等的时候，如果 midIndex 为0或者前一个数比 target 小那么就找到了第一个等于给定值的元素，直接返回if (midIndex === 0 || arr[midIndex - 1] < target) return midIndex// 否则高位下标为中间下标减1，继续查找highIndex = midIndex - 1}}return -1
}

实际上，除了有序的数组可以使用，还有一种特殊的数组可以应用，那就是轮转后的有序数组

有序数组即一个有序数字以某一个数为轴，将其之前的所有数都轮转到数组的末尾所得

例如，[4, 5, 6, 7, 0, 1, 2]就是一个轮转后的有序数组

该数组的特性是存在一个分界点用来分界两个有序数组，如下：

分界点有如下特性：

分界点元素 >= 第一个元素
分界点元素 < 第一个元素

代码实现如下：

function search (nums, target) {// 如果为空或者是空数组的情况if (nums == null || !nums.length) {return -1;}// 搜索区间是前闭后闭let begin = 0,end = nums.length - 1;while (begin <= end) {// 下面这样写是考虑大数情况下避免溢出let mid = begin + ((end - begin) >> 1);if (nums[mid] == target) {return mid;}// 如果左边是有序的if (nums[begin] <= nums[mid]) {//同时target在[ nums[begin],nums[mid] ]中，那么就在这段有序区间查找if (nums[begin] <= target && target <= nums[mid]) {end = mid - 1;} else {//否则去反方向查找begin = mid + 1;}//如果右侧是有序的} else {//同时target在[ nums[mid],nums[end] ]中，那么就在这段有序区间查找if (nums[mid] <= target && target <= nums[end]) {begin = mid + 1;} else {end = mid - 1;}}}return -1;
};

对比普通的二分查找法，为了确定目标数会落在二分后的哪个部分，我们需要更多的判定条件。