二分查找(有序数组)

上传者：蒋卫宏
|
上传时间：2015-04-26
|
密次下载

二分查找(有序数组)

思考题：

给定一个有序的数组，准备将一个元素插入到该数组中，还要保证该数组是有序。问：如何获取该元素的插入的位置。

思路：

1、看到有序数组，还要查找数组中的元素，首先就要想到二分查找

2、分两种情况:

2.1 该插入元素在数组中存在。找出对应元素的角标就行

2.2 要插入元素在数组中不存在。找出与该值最接近元素角标

private static int getIndexOfInsertArr(int[] arr,int num) {

int max,min,mid;

min = 0;

max = arr.length-1;

while(min<=max)

{

mid = (max+min)>>1;

if(num>arr[mid])

min = mid + 1;

else if(num<arr[mid])

max = mid - 1;

else

return mid;

}

return min+1;

}

二分查找是算法设计的基本功。它的思想很简单：分而治之，即通过把一个大问题分解成多个子问题来降低解题的复杂度。

上面程序，无论怎么看都没什么不妥，但在一些极端的情况下，min与max求和的时候可能会导致溢出。（32位有符号整数可以表示的范围是 -2147483648 ~ 2147483647）所以我们最好把它写成 mid = min + (max - min)/2;

下载文档

网友关注

网友关注视频

冀教版小学英语四年级下册Lesson2授课视频

沪教版牛津小学英语（深圳用）四年级下册 Unit 7

沪教版八年级下册数学练习册一次函数复习题B组（P11）

【部编】人教版语文七年级下册《过松源晨炊漆公店（其五）》优质课教学视频+PPT课件+教案，辽宁省

二年级下册数学第三课搭一搭⚖⚖

沪教版牛津小学英语（深圳用）六年级下册 Unit 7

第8课对称剪纸_第一课时(二等奖)(沪书画版二年级上册)_T3784187

8 随形想象_第一课时(二等奖)(沪教版二年级上册)_T3786594

化学九年级下册全册同步人教版第25集生活中常见的盐（二）

【部编】人教版语文七年级下册《泊秦淮》优质课教学视频+PPT课件+教案，辽宁省

青岛版教材五年级下册第四单元（走进军营——方向与位置）用数对确定位置（一等奖）

沪教版牛津小学英语（深圳用）五年级下册 Unit 12

冀教版小学数学二年级下册第二单元《租船问题》

冀教版小学数学二年级下册第二单元《余数和除数的关系》

【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案，安徽省

沪教版八年级下册数学练习册21.3（3）分式方程P17

冀教版小学英语五年级下册lesson2教学视频(2)

30.3 由不共线三点的坐标确定二次函数_第一课时(市一等奖)(冀教版九年级下册)_T144342

小学英语单词

【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案，安徽省

外研版英语三起6年级下册（14版）Module3 Unit2

每天日常投篮练习第一天森哥打卡上脚 Nike PG 2 如何调整运球跳投手感？

沪教版牛津小学英语（深圳用）四年级下册 Unit 12

飞翔英语—冀教版(三起)英语三年级下册Lesson 2 Cats and Dogs

七年级英语下册上海牛津版 Unit3

北师大版数学四年级下册第三单元第二节小数点搬家

第12章圆锥曲线_12.7 抛物线的标准方程_第一课时(特等奖)(沪教版高二下册)_T274713

第五单元民族艺术的瑰宝_15. 多姿多彩的民族服饰_第二课时(市一等奖)(岭南版六年级上册)_T129830

【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案，安徽省

第4章幂函数、指数函数和对数函数（下）_六指数方程和对数方程_4.7 简单的指数方程_第一课时(沪教版高一下册)_T1566237

精品推荐

营造良好的企业文化

分类导航

生物学

蒋卫宏

此文档贡献者

2015-04-26
贡献时间
密
下载次数

教育资源为主的文档平台

文档分类