二分查找(有序数组)

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

下载文档

网友关注

Jefferies-Huaneng Power（0902.HK）1Q First Take: Strong Beat on Coal Costs

华安证券-2015年3月份PMI数据点评：大小企业分化，经济难言企稳

J.P.Morgan-TCL Multimedia（1070.HK）Lifting PT to HK$6.8-New online revenue stream

卫士通：2012年年度报告摘要

中国银行-宏观观察2015年第10期：经济新常态及宏观调控新框架

民生证券-宏观区域经济系列报告：冬天里的一把火，当冬奥会遇上京津冀

兴业证券-美国数据一周详解：Markit制造业PMI快速反弹

J.P.Morgan-Daphne International（0210.HK）Downgrade to UW - 1Q15 SSS Declining 16%; Risk that FY15 Will Be Loss-Making

Jefferies-Gaming：Structural Changes to Benefit the Sector in the Long Run

宏观经济形势及投资分析

J.P. Morgan-First to Market

华泰证券-从社保扩大投资范围谈起：一举多得的存量债务解决方案猜想

山西证券-国内外经济一周数据及政策点评：政策稳增长五箭齐发，欧洲且起舞美国分化

Morgan Stanley-Hang Seng Bank( 0011.HK）Becoming a Mid-/High-Teens Annual Compounder Again – OW

第十章中国宏观经济问题

说金论赢：金银指标修复调整留意欧洲局势突变

Galaxy International Securities-Yum Cha

Daiwa Capital-China Resources Enterprise（0291.HK）Beer business to be main focus

J.P.Morgan-JPM Asia Telco Investing our Recommendations：Back Testing Analysis: 17th Apr 2015

UOBKayHian-Regional Morning Notes

光大证券-国际经济周报：非农就业远低预期打压美元，关注下周希腊债务风险

中国银行-中国经济金融展望报告

国泰君安-点评央行和财政部330救房市：copy2009年做法，短期春药改革麻药

高华证券-GOAL，全球资产投资机会定位：将债券上调至高配；股市下跌风险上升

高华证券-在低回报离散度的市场上选股：在宏观面推动的市场上获得超额回报的选股指南

高华证券-中国经济数据简评：2015年3月份数据前瞻，实体经济增速温和反弹、通胀率和贸易顺差回落、货币状况放松

华泰证券-2015年第11周宏观周报：工业利润继续恶化，一带一路扩展空间

华泰证券-博鳌论坛相关新闻点评：“一带一路”与亚投行的影响

Jefferies-China Mobile Limited（0941.HK）1Q15 Results Review

Jefferies-China Property：Supporting Sales Data Emerging to Catalyze

网友关注视频

第19课我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386

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

8.对剪花样_第一课时(二等奖)(冀美版二年级上册)_T515402

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

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

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

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

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

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

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

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

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

人教版二年级下册数学

人教版历史八年级下册第一课《中华人民共和国成立》

冀教版英语三年级下册第二课

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

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

三年级英语单词记忆下册（沪教版）第一二单元复习

北师大版小学数学四年级下册第15课小数乘小数一

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

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

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

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

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

化学九年级下册全册同步人教版第18集常见的酸和碱（二）

苏科版数学八年级下册第八章第二节可能性的大小

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

【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示

化学九年级下册全册同步人教版第22集酸和碱的中和反应（一）

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

精品推荐

营造良好的企业文化

分类导航

生物学

蒋卫宏

此文档贡献者

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

教育资源为主的文档平台

文档分类