二分查找法思想 二分查找的思想

二分查找法思想 二分查找的思想

算法:当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。

  基本思想:假设数据是按升序排序的,对于给定值x,从序列的中间位置开始比较,如果当前位置值等于x,则查找成功;若x小于当前位置值,则在数列的前半段中查找;若x大于当前位置值则在数列的后半段中继续查找,直到找到为止。

  假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.

  1.开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为mid>x,故应在前半段中查找。

  2.令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。

  3.令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。

  如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。

  例:在有序的有N个元素的数组中查找用户输进去的数据x。

  算法如下:

  1.确定查找范围front=0,end=N-1,计算中项mid(front+end)/2。

  2.若a[mid]=x或front>=end,则结束查找;否则,向下继续。

  3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内,则把mid+1的值赋给front,并重新计算mid,转去执行步骤2;若a[mid]>x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。

在顺序表(3,6,8,10,12,15,16,18,21,25,30)中,用二分法查找关键码值11,所需的关键码比较次数为(B)
A. 2
B. 3
C. 4
D. 5

备注:原文来自于http://baike.baidu.com/view/75441.htm

  

爱华网本文地址 » http://www.aihuau.com/a/25101017/352470.html

更多阅读

小方巾的系法图解 小方巾的系法图解视频

家里的丝巾围巾多不胜数,小方巾、长围巾、披肩,啥都有。小方巾怎么系?这里有小方巾的七种常见系法,下面就手把手教你小方巾各种系法。小方巾的系法图解——步骤/方法小方巾的系法图解 1、小蝴蝶结。小技巧:因为要用长度较短的方巾系出小

窗花的简单剪法 圆形双喜字的简单剪法

窗花的简单剪法——简介上幼儿园和小学的时候,老师最喜欢教我们做手工,而手工里最常见的必须就是剪窗花哇,那个时候剪了几个比较漂亮的,都会获准带回家,献宝似的交给大人,贴在门上或是窗户上。窗花的简单剪法——方法/步骤窗花的简单剪法

超详细的鱼骨辫编法 简单鱼骨辫的编法图解

超详细的鱼骨辫编法——简介鱼骨辫一直深受MM们的喜爱,但是怎样才能编得更加完美呢?来这里看看超详细的鱼骨辫编法图解吧,简单的编法,却是女生们不得不学会的发型编法。超详细的鱼骨辫编法——工具/原料皮筋或者发饰超详细的鱼骨辫编

来自星星的你折法 吸管星星的折法视频

来自星星的你折法——简介用彩色的吸管折成漂亮的心来自星星的你折法——工具/原料手工专用星星管一条来自星星的你折法——方法/步骤来自星星的你折法 1、

声明:《二分查找法思想 二分查找的思想》为网友年轻无极限分享!如侵犯到您的合法权益请联系我们删除