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

自建网站卖东西电子商务与网络营销教案

自建网站卖东西,电子商务与网络营销教案,界首市合肥网络推广外包,重庆手机网站制作二分查找详解与实现:左闭右闭区间(二分模板 1) 个人比较习惯的二分模版 一、引言 二分查找(Binary Search)是一个高效的搜索算法,它在有序数组中以对数时间复杂度 O(log n) 搜索目标元素的位置。二分查找…

二分查找详解与实现:左闭右闭区间(二分模板 1)

个人比较习惯的二分模版

一、引言

二分查找(Binary Search)是一个高效的搜索算法,它在有序数组中以对数时间复杂度 O(log n) 搜索目标元素的位置。二分查找非常适合用在「值单调」的问题中,如在一个升序数组中查找某个值是否存在、某个条件的最小值/最大值等。

本篇文章主要介绍一种最常用且稳定的二分查找模板:左闭右闭区间 [left, right] 的实现方法。


二、适用前提

使用二分查找有以下几个前提条件:

  1. 数组必须有序(升序或降序均可)
  2. 支持随机访问(如数组或 vector
  3. 可比较目标值与当前值的大小关系

三、基本思想

在二分查找中,我们反复将搜索区间划分为两半,并根据目标值的位置来缩小搜索范围。

区间定义:左闭右闭 [left, right]

  • 包括 leftright 所指的元素,即搜索区间为 a[left] ~ a[right]
  • 因此当 left == right 时,区间仍然有效,循环条件为 left <= right

四、为什么这样写?三点解释

---- int mid = left + (right - left) / 2 的原因?

使用 (left + right) / 2 有溢出风险,尤其在 leftright 很大时可能导致整型溢出,因此推荐使用:

int mid = left + (right - left) / 2;

或者位运算版本:

int mid = left + ((right - left) >> 1);

---- 为什么 while (left <= right)

因为我们采用的是左闭右闭区间 [left, right],在 left == righta[left] 依然是有效元素,因此需要用 <=

----为什么 right = mid - 1left = mid + 1

  • a[mid] > target:说明目标在左边 → 舍弃 mid 本身(因为不等于目标) → right = mid - 1
  • a[mid] < target:目标在右边 → 舍弃 mid 本身 → left = mid + 1

五、完整代码实现(含详尽注释)

#include <iostream>
#include <vector>
using namespace std;int main()
{// 示例有序数组(升序)vector<int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };// 输入要查找的目标值int target;cout << "请输入要查找的目标值: ";cin >> target;// 定义左闭右闭区间 [left, right]int left = 0;int right = a.size() - 1;// 二分查找过程while (left <= right){// 计算中间索引,防止溢出的写法int mid = left + (right - left) / 2;// 如果找到了目标if (a[mid] == target){cout << "目标值 " << target << " 的索引是: " << mid << endl;return 0;}// 如果中间值大于目标,目标在左区间else if (a[mid] > target){right = mid - 1;}// 如果中间值小于目标,目标在右区间else{left = mid + 1;}}// 若执行到此处,说明未找到目标值cout << "目标值 " << target << " 不存在于数组中" << endl;cout << "-1" << endl;return 0;
}

六、常见错误总结

错误写法错误原因
while (left < right)会漏掉最后一个元素的判断。若目标值恰好是 a[right],会漏查
mid = (left + right)/2有可能溢出
区间定义不清晰容易导致死循环或漏查,建议固定一种模板

七、模板通用性说明

左闭右闭区间的模板是最常用的写法,它的好处是逻辑清晰,循环条件为 left <= right,比「左闭右开」更容易处理收敛边界情况。

http://www.dinnco.com/news/35235.html

相关文章:

  • 小型教育网站的开发与建设论文惠州网站建设
  • 商丘市做1企业网站的公司东莞网站推广企业
  • 做网站工作好么win10优化大师免费版
  • 国际贸易网站哪家好百度付费推广
  • 大连 做网站网站数据统计
  • 聊城做网站费用价格苏州整站优化
  • 在国外做网站怎么做推广让别人主动加我
  • 做动画网站怎么建公司网站
  • 用php做美食网站新东方小吃培训价格表
  • 做义工的靠谱网站注册推广赚钱一个10元
  • 网站开发逻辑关于华大18年专注seo服务网站制作应用开发
  • 牡丹江疫情最新政策厦门seo代理商
  • 海南网站建设哪家不错免费发布信息
  • 做非法集资资讯的网站西安网站建设公司十强
  • 广州营销型网站建设公司哪家靠谱百度收录查询方法
  • 网站建设标语辅导机构
  • 网站中的搜索框怎么做网站seo优化案例
  • 安监网站如何做紧急预案备案推广方案框架
  • 慈溪网站建设哪家好免费网页制作成品
  • 网站如何制作 优帮云会计培训机构排名前十
  • 云空间布置网站百度推广一天烧几千
  • 凡科做网站有什么用广州疫情最新动态
  • 如何搜名字搜到自己做的网站如何在百度上建立网站
  • 无锡网站建设选众鼎色盲
  • php网上商城系统seo信息优化
  • 电子商务网站开发平台如何免费注册网站平台
  • Wordpress漂亮免费主题seo算法是什么
  • 北京工作室网站建设百度seo关键词优化工具
  • 中国网站名二级域名网站查询入口
  • 建设的网站属于固定资产么百度公司招聘