二分查找(有序数组)

上传者：蒋卫宏
|
上传时间：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;

下载文档

网友关注

一师一优课政府的职能：管理与服务教学设计余

台北市立大安国民中学九十七学年度第一学期学生注册须知

2014年秋季学期龙田镇初级中学安全教育工作研讨会方案

高楼坪民族中学2013

金沙县后山乡组织教师到沙土镇观摩学习义务教育均衡发展工作

教育理念名言

学期初教学简报

网友关注视频

冀教版小学数学二年级下册1

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

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

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

外研版英语七年级下册module3 unit2第一课时

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

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

《空中课堂》二年级下册数学第一单元第1课时

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

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

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

二年级下册数学第一课

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

外研版八年级英语下学期 Module3

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

苏科版数学八年级下册9.2《中心对称和中心对称图形》

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

冀教版英语五年级下册第二课课程解读

沪教版八年级下次数学练习册21.4（2）无理方程P19

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

冀教版小学数学二年级下册第二单元《有余数除法的竖式计算》

3月2日小学二年级数学下册（数一数）

冀教版小学数学二年级下册第二周第2课时《我们的测量》宝丰街小学庞志荣.mp4

北师大版数学四年级下册第三单元第四节街心广场

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

二次函数求实际问题中的最值_第一课时(特等奖)(冀教版九年级下册)_T144339

外研版英语三起5年级下册（14版）Module3 Unit1

19 爱护鸟类_第一课时(二等奖)(桂美版二年级下册)_T502436

第五单元民族艺术的瑰宝_16. 形形色色的民族乐器_第一课时(岭南版六年级上册)_T3751175

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

精品推荐

营造良好的企业文化

分类导航

生物学

蒋卫宏

此文档贡献者

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

教育资源为主的文档平台

文档分类