顺义做网站的公司,网站页面设计基础教程,怎样开一个自己的公司,监理网站二分法查找#xff0c;也称作二分查找或折半查找#xff0c;是一种在有序数组中快速查找特定元素的算法。它采用分治法思想#xff0c;通过将问题划分为规模更小的子问题#xff0c;并且通过对子问题的查找来解决原问题。
二分法查找的思路是不断地将数组一分为二#xf…二分法查找也称作二分查找或折半查找是一种在有序数组中快速查找特定元素的算法。它采用分治法思想通过将问题划分为规模更小的子问题并且通过对子问题的查找来解决原问题。
二分法查找的思路是不断地将数组一分为二然后判断目标值在哪一部分进而在该部分继续进行二分查找。具体步骤如下
首先设置左边界 left 为0右边界 right 为数组的长度减1。然后计算中间值 mid 为左边界与右边界的平均值并取整。接着比较中间值 arr[mid] 与目标值 target 的大小。如果相等则返回索引 mid。如果 arr[mid] 大于 target说明目标值在左半部分将右边界 right 更新为 mid-1。如果 arr[mid] 小于 target说明目标值在右半部分将左边界 left 更新为 mid1。重复步骤2至5直到左边界大于右边界表示数组中无目标值返回-1。 #mermaid-svg-mAofW1CfWVJY8PY2 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-mAofW1CfWVJY8PY2 .error-icon{fill:#552222;}#mermaid-svg-mAofW1CfWVJY8PY2 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-mAofW1CfWVJY8PY2 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-mAofW1CfWVJY8PY2 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-mAofW1CfWVJY8PY2 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-mAofW1CfWVJY8PY2 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-mAofW1CfWVJY8PY2 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-mAofW1CfWVJY8PY2 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-mAofW1CfWVJY8PY2 .marker.cross{stroke:#333333;}#mermaid-svg-mAofW1CfWVJY8PY2 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-mAofW1CfWVJY8PY2 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-mAofW1CfWVJY8PY2 .cluster-label text{fill:#333;}#mermaid-svg-mAofW1CfWVJY8PY2 .cluster-label span{color:#333;}#mermaid-svg-mAofW1CfWVJY8PY2 .label text,#mermaid-svg-mAofW1CfWVJY8PY2 span{fill:#333;color:#333;}#mermaid-svg-mAofW1CfWVJY8PY2 .node rect,#mermaid-svg-mAofW1CfWVJY8PY2 .node circle,#mermaid-svg-mAofW1CfWVJY8PY2 .node ellipse,#mermaid-svg-mAofW1CfWVJY8PY2 .node polygon,#mermaid-svg-mAofW1CfWVJY8PY2 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-mAofW1CfWVJY8PY2 .node .label{text-align:center;}#mermaid-svg-mAofW1CfWVJY8PY2 .node.clickable{cursor:pointer;}#mermaid-svg-mAofW1CfWVJY8PY2 .arrowheadPath{fill:#333333;}#mermaid-svg-mAofW1CfWVJY8PY2 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-mAofW1CfWVJY8PY2 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-mAofW1CfWVJY8PY2 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-mAofW1CfWVJY8PY2 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-mAofW1CfWVJY8PY2 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-mAofW1CfWVJY8PY2 .cluster text{fill:#333;}#mermaid-svg-mAofW1CfWVJY8PY2 .cluster span{color:#333;}#mermaid-svg-mAofW1CfWVJY8PY2 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-mAofW1CfWVJY8PY2 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 是 否 是 否 是 否 开始 初始化左指针l和右指针r 判断l是否大于r 找到目标值 判断中间值是否等于目标值 找到目标值 判断中间值是否大于目标值 在左半部分继续查找 在右半部分继续查找 说明
开始时初始化左指针l指向数组的首元素右指针r指向数组的尾元素。判断左指针l是否大于右指针r如果是则表示没有找到目标值结束查找。每次都取左指针l和右指针r中间的元素作为中间值。判断中间值是否等于目标值如果是则表示找到目标值结束查找。如果中间值大于目标值说明目标值在左半部分更新右指针r为中间值的前一个位置继续查找。如果中间值小于目标值说明目标值在右半部分更新左指针l为中间值的后一个位置继续查找。继续进行以上步骤直到找到目标值或者确定没有目标值。
示例代码
function binarySearch(arr, target) {let left 0; // 定义左边界指针为数组的起始位置let right arr.length - 1; // 定义右边界指针为数组的末尾位置while (left right) { // 当左边界指针小于等于右边界指针时执行循环let mid Math.floor((left right) / 2); // 计算中间元素的位置向下取整if (arr[mid] target) { // 如果中间元素等于目标值return mid; // 返回中间元素的位置} else if (arr[mid] target) { // 如果中间元素小于目标值left mid 1; // 移动左边界指针到中间元素的下一个位置} else { // 如果中间元素大于目标值right mid - 1; // 移动右边界指针到中间元素的前一个位置}}return -1; // 如果循环结束仍未找到目标值则返回-1
}// 示例使用
let arr [1, 3, 5, 7, 9];
let target 5;let result binarySearch(arr, target);
console.log(result); // 输出 2在上面的示例中提供了一个有序数组 arr 和目标值 target然后调用 binarySearch 函数进行二分查找。最后输出的结果为目标值在数组中的索引如果不存在则返回-1。
左边界指针右边界指针中间元素位置中间元素值目标值结果042552
