• 售前

  • 售后

热门帖子
入门百科

二分、三分入门

[复制链接]
123457108 显示全部楼层 发表于 2022-1-16 06:32:59 |阅读模式 打印 上一主题 下一主题
二分、三分入门


小故事

一天DOGGOD_Q到图书馆借了 N 本书,出图书馆的时间,警报响了,于是保安把DOGGOD_Q拦下,要查抄一下哪本书没有登记出借。DOGGOD_Q正预备把每一本书在报警器下过一下,以找出引发警报的书,但是保安袒露不屑的眼神:你连二分查找都不会吗?于是保安把书分成两堆,让第一堆过一下报警器,报警器响;于是再把这堆书分成两堆…… 终极,检测了 logN 次之后,保安乐成的找到了那本引起警报的书,袒露了得意和讽刺的笑脸。于是DOGGOD_Q背着剩下的书走了。 今后,图书馆丢了 N - 1 本书。
1. 二分法简介

二分查找(binary search),也称折半搜索(half-interval search)、对数搜索(logarithmic search),是用来在一个有序数组中查找某一元素的算法。(以是图书馆丢了N-1本书)
1.1 时间复杂度

二分查找的最优时间复杂度为O(1) 。
二分查找的均匀时间复杂度和最坏时间复杂度均为O(log n) 。由于在二分搜索过程中,算法每次都把查询的区间减半,以是对于一个长度为 的数组,至多会举行O(log n) 次查找。
1.2 空间复杂度

递归版本的二分查找的空间复杂度为O(log n) 。
非递归版本的二分查找的空间复杂度为O(1) 。
1.3 工作原理

以在一个升序数组中查找一个数为例。
它每次观察数组当前部分的中心元素,如果中心元素刚好是要找的,就竣事搜索过程;如果中心元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果中心元素大于所查找的值同理,只需到左侧查找。
1.3.1 递归版本

  1. int binary_search1(int left, int right, int target)
  2. {
  3.     if (left > right)
  4.         return -1;
  5.     int mid = left + (right - left) >> 1;
  6.     if (arr[mid] == target)
  7.         return mid;
  8.     else if (arr[mid] < target)
  9.         return (mid + 1, right, target);
  10.     else
  11.         return (left, mid - 1, target);
  12. }
复制代码
1.3.2 非递归版本

  1. int binary_search2(int left, int right, int target)
  2. {
  3.     if (left > right)
  4.         return -1;
  5.     while (left <= right)
  6.     {
  7.         int mid = left + ((right - left) >> 1);
  8.         if (arr[mid] == target)
  9.             return mid;
  10.         else if (arr[mid] < target)
  11.             left = mid + 1;
  12.         else
  13.             right = mid - 1;
  14.     }
  15.     return -1;
  16. }
复制代码
1.3.3 STL 的二分查找

在升序序列中lower_bound返回第一个大于便是参数target的序列值的迭代器。
在升序序列中upper_bound返回第一个大于参数target的序列值的迭代器。
lower_bound(): 返回一个迭代器,指向键值>= key的第一个元素。
upper_bound(): 返回一个迭代器,指向键值>key的第一个元素。
[code]int arr[12] = {1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4};cout

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作