-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbinary_search.html
More file actions
666 lines (529 loc) · 82.4 KB
/
binary_search.html
File metadata and controls
666 lines (529 loc) · 82.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
<!DOCTYPE html>
<html>
<head>
<title>
详解二分查找算法 | 雅乐网 </title>
<meta charset="UTF-8" />
<meta name="renderer" content="webkit">
<link rel="stylesheet" href="http://www.yalewoo.com/wp-content/themes/YLW3_lite/style.css" type="text/css" />
<link rel="alternate" type="application/rss+xml" title="RSS 2.0" href="http://www.yalewoo.com/feed" />
<!-- All in One SEO Pack 2.3.12.1 by Michael Torbert of Semper Fi Web Design[-1,-1] -->
<meta name="description" content="二分查找是一个用于有序数组查找的常用算法。它的基本思想非常简单，以至于我们都会自认为已经掌握。但是，纸上得来终觉浅，当实际动手的时候，还是会发现许多问题。下面雅乐网整理了一下二分查找算法的实现。 思想 先看看维基百科的说法： 二分查找的搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找成功；如果" />
<link rel="canonical" href="http://www.yalewoo.com/binary_search.html" />
<!-- /all in one seo pack -->
<link rel="alternate" type="application/rss+xml" title="雅乐网 » 详解二分查找算法评论Feed" href="http://www.yalewoo.com/binary_search.html/feed" />
<link rel='stylesheet' id='crayon-css' href='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/css/min/crayon.min.css?ver=_2.7.2_beta' type='text/css' media='all' />
<link rel='stylesheet' id='crayon-theme-classic-css' href='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/themes/classic/classic.css?ver=_2.7.2_beta' type='text/css' media='all' />
<link rel='stylesheet' id='crayon-font-consolas-css' href='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/fonts/consolas.css?ver=_2.7.2_beta' type='text/css' media='all' />
<script type='text/javascript' src='https://lib.sinaapp.com/js/jquery/1.8.2/jquery.min.js'></script>
<script type='text/javascript'>
/* <![CDATA[ */
var CrayonSyntaxSettings = {"version":"_2.7.2_beta","is_admin":"0","ajaxurl":"http:\/\/www.yalewoo.com\/wp-admin\/admin-ajax.php","prefix":"crayon-","setting":"crayon-setting","selected":"crayon-setting-selected","changed":"crayon-setting-changed","special":"crayon-setting-special","orig_value":"data-orig-value","debug":""};
var CrayonSyntaxStrings = {"copy":"Press %s to Copy, %s to Paste","minimize":"Click To Expand Code"};
/* ]]> */
</script>
<script type='text/javascript' src='http://www.yalewoo.com/wp-content/plugins/crayon-syntax-highlighter/js/min/crayon.min.js?ver=_2.7.2_beta'></script>
<link rel='prev' title='linux可以开始运行apk了' href='http://www.yalewoo.com/chromeos_apk.html' />
<link rel='next' title='冒泡排序：思路、详解、C语言实现' href='http://www.yalewoo.com/bubble_sort.html' />
<link rel='shortlink' href='http://www.yalewoo.com/?p=824' />
<link rel="stylesheet" href="http://www.yalewoo.com/wp-content/plugins/wp-content-index/style.css" type="text/css" media="all" />
<!-- Start Of Script Generated By WP-PostViews -->
<script type="text/javascript">
/* <![CDATA[ */
jQuery.ajax({type:'GET',url:'http://www.yalewoo.com/wp-admin/admin-ajax.php',data:'postviews_id=824&action=postviews',cache:false});/* ]]> */
jQuery(document).ready(function() {
var ajax_data = {
action: "show_postview",
postviews_id: 824
};
$.post("http://www.yalewoo.com/wp-admin/admin-ajax.php", ajax_data,
function(data) {
$('.meta-view').html(data);
});
return false;
});
</script>
<!-- End Of Script Generated By WP-PostViews -->
<script src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/jquery.lazyload.min.js" type="text/javascript"></script>
<script type="text/javascript">
$(function() {
$("#secondary img").lazyload({
effect:"fadeIn"
});
});
$(function() {
$("img").lazyload({
effect:"fadeIn"
});
});
</script>
<!--[if lte IE 8]><script>document.write("<p style=\"color:red;font-size:40px;\">你正在使用 Internet Explorer 的过期版本（IE6、IE7、IE8）<br/>请<a href=\"#\" style=\"color:blue;\">升级您的浏览器</a>获得更好的浏览体验。</p>");</script><![endif]-->
</head><body>
<header id="topheader">
<hgroup>
<h1><a href = "http://www.yalewoo.com">雅乐网</a>
</h1>
<h2>计算机技术博客</h2>
</hgroup>
<div id="top_menu">
<div class="menu-%e6%9c%80%e9%a1%b6%e7%ab%af-container"><ul id="menu-%e6%9c%80%e9%a1%b6%e7%ab%af" class="menu"><li id="menu-item-663" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-663"><a href="http://www.yalewoo.com/about">关于本站</a></li>
<li id="menu-item-662" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-662"><a href="http://www.yalewoo.com/updates">雅乐网更新记录</a></li>
<li id="menu-item-661" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-661"><a target="_blank" href="http://www.yalewoo.com/old0/">老版网站</a></li>
</ul></div> <form method="get" id="searchform" action="http://www.yalewoo.com/">
<div>
<input type="text" value="" name="s" id="s" size="15" />
<input type="submit" id="searchsubmit" value="Search" />
</div>
</form> </div>
</header>
<nav class="main_nav">
<div class="menu-%e4%b8%bb%e8%8f%9c%e5%8d%9520171106-container"><ul id="menu-%e4%b8%bb%e8%8f%9c%e5%8d%9520171106" class="menu"><li id="menu-item-3235" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-home menu-item-3235"><a href="http://www.yalewoo.com/">首页</a></li>
<li id="menu-item-3237" class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor menu-item-has-children menu-item-3237"><a href="http://www.yalewoo.com/programming">编程</a>
<ul class="sub-menu">
<li id="menu-item-3238" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3238"><a href="http://www.yalewoo.com/programming/c_cpp">C/C++</a></li>
<li id="menu-item-3243" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3243"><a href="http://www.yalewoo.com/programming/data_structure">数据结构</a></li>
<li id="menu-item-3244" class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor current-menu-parent current-post-parent menu-item-3244"><a href="http://www.yalewoo.com/programming/basic_algorithm">算法</a></li>
<li id="menu-item-3240" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3240"><a href="http://www.yalewoo.com/programming/online_judge">OJ刷题</a></li>
<li id="menu-item-3239" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3239"><a href="http://www.yalewoo.com/programming/linux">Linux</a></li>
<li id="menu-item-3241" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3241"><a href="http://www.yalewoo.com/programming/web">Web</a>
<ul class="sub-menu">
<li id="menu-item-3242" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3242"><a href="http://www.yalewoo.com/programming/web/wordpress">wordpress</a></li>
</ul>
</li>
</ul>
</li>
<li id="menu-item-3245" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3245"><a href="http://www.yalewoo.com/algorithm">算法</a>
<ul class="sub-menu">
<li id="menu-item-3248" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3248"><a href="http://www.yalewoo.com/algorithm/maths">数学</a></li>
<li id="menu-item-3246" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3246"><a href="http://www.yalewoo.com/algorithm/ml_notes">机器学习</a></li>
<li id="menu-item-3281" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3281"><a href="http://www.yalewoo.com/algorithm/deep_learning">深度学习</a></li>
<li id="menu-item-3247" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3247"><a href="http://www.yalewoo.com/algorithm/python">python</a></li>
<li id="menu-item-3253" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3253"><a href="http://www.yalewoo.com/algorithm/%e7%a4%be%e5%9b%a2%e6%a3%80%e6%b5%8b">社团检测</a></li>
</ul>
</li>
<li id="menu-item-3254" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3254"><a href="http://www.yalewoo.com/tools">工具教程</a>
<ul class="sub-menu">
<li id="menu-item-3255" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3255"><a href="http://www.yalewoo.com/tools/git">Git/GitHub</a></li>
<li id="menu-item-3256" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3256"><a href="http://www.yalewoo.com/tools/sublime_text">Sublime Text</a></li>
<li id="menu-item-3257" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3257"><a href="http://www.yalewoo.com/tools/vs2013">VS2013</a></li>
<li id="menu-item-3259" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3259"><a href="http://www.yalewoo.com/tools/browser">浏览器</a></li>
<li id="menu-item-3258" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3258"><a href="http://www.yalewoo.com/tools/other_tools">其他工具</a></li>
</ul>
</li>
<li id="menu-item-3260" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3260"><a href="http://www.yalewoo.com/excellent_softwares">软件推荐</a>
<ul class="sub-menu">
<li id="menu-item-3261" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3261"><a href="http://www.yalewoo.com/excellent_softwares/zip">压缩加密</a></li>
<li id="menu-item-3262" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3262"><a href="http://www.yalewoo.com/excellent_softwares/pictools">图片工具</a></li>
<li id="menu-item-3263" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3263"><a href="http://www.yalewoo.com/excellent_softwares/media_tools">多媒体</a></li>
<li id="menu-item-3264" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3264"><a href="http://www.yalewoo.com/excellent_softwares/safe_software">安全清理</a></li>
<li id="menu-item-3265" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3265"><a href="http://www.yalewoo.com/excellent_softwares/android">安卓</a></li>
<li id="menu-item-3266" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3266"><a href="http://www.yalewoo.com/excellent_softwares/utility">实用工具</a></li>
<li id="menu-item-3267" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3267"><a href="http://www.yalewoo.com/excellent_softwares/search_tools">搜索词典</a></li>
<li id="menu-item-3268" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3268"><a href="http://www.yalewoo.com/excellent_softwares/efficiency_tools">效率提升</a></li>
<li id="menu-item-3269" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3269"><a href="http://www.yalewoo.com/excellent_softwares/programming_tools">编程开发</a></li>
<li id="menu-item-3270" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3270"><a href="http://www.yalewoo.com/excellent_softwares/internet_software">网络软件</a></li>
<li id="menu-item-3271" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3271"><a href="http://www.yalewoo.com/excellent_softwares/edit_and_reading">阅读编辑</a></li>
</ul>
</li>
<li id="menu-item-3272" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3272"><a href="http://www.yalewoo.com/it_resource">资源</a>
<ul class="sub-menu">
<li id="menu-item-3273" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3273"><a href="http://www.yalewoo.com/it_resource/good_websites">好网站</a></li>
<li id="menu-item-3274" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3274"><a href="http://www.yalewoo.com/it_resource/stuff">好资料</a></li>
<li id="menu-item-3275" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3275"><a href="http://www.yalewoo.com/it_resource/how">授人以渔</a></li>
<li id="menu-item-3276" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3276"><a href="http://www.yalewoo.com/it_resource/ebooks-share">电子书</a></li>
</ul>
</li>
<li id="menu-item-3277" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-3277"><a href="http://www.yalewoo.com/learning">我爱学习</a>
<ul class="sub-menu">
<li id="menu-item-3278" class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3278"><a href="http://www.yalewoo.com/learning/popular_science">科普</a></li>
</ul>
</li>
<li id="menu-item-3280" class="menu-item menu-item-type-post_type menu-item-object-page menu-item-3280"><a href="http://www.yalewoo.com/about">关于本站</a></li>
</ul></div></nav>
<script type="text/javascript" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/dianzan.js"></script>
<div id="mbxdh">
<div>
<a href="http://www.yalewoo.com/programming">编程</a> » <a href="http://www.yalewoo.com/programming/basic_algorithm">算法</a> » 详解二分查找算法 </div>
</div>
<div id="container">
<section class="whole_article" id="article-824">
<article class="post-824 post type-post status-publish format-standard hentry category-basic_algorithm tag-210 tag-157" id="entry">
<h2 id="article-title">
<span class = "title-meta-yuanchuang title-meta-ico"></span>
<a href="http://www.yalewoo.com/binary_search.html" title="详解二分查找算法">详解二分查找算法</a>
<span class = "title-meta-huo title-meta-ico"></span>
</h2>
<div class="post-meta">
<span class="meta-author meta-ico"><a href="http://www.yalewoo.com/author/yalewoo" title="由yalewoo发布" rel="author">yalewoo</a> </span>
<span class="meta-time meta-ico"> 最后修改于 2015-03-14</span>
发表于 2014-09-30
<span class="meta-view meta-ico">2,190</span>
<span class="meta-comment meta-ico"><a href="http://www.yalewoo.com/binary_search.html#comments">1</a></span>
<br><br>
<span class="meta-category meta-ico"> <a href="http://www.yalewoo.com/programming/basic_algorithm" rel="category tag">算法</a> </span>
<span class="meta-category meta-ico"> <a href="http://www.yalewoo.com/tag/%e6%9f%a5%e6%89%be" rel="tag">查找</a>, <a href="http://www.yalewoo.com/tag/%e7%ae%97%e6%b3%95" rel="tag">算法</a> </span>
</div>
<div id="article-content">
<div id="content-index" class="content-index" style="margin:0 0 10px 10px;float:right;"><span class="content-index-toctoggle">[<a id="content-index-togglelink" href="javascript:content_index_toggleToc()">目录开关</a>]</span>
<script type="text/javascript" language="javascript">
window.content_index_showTocToggle=true;function content_index_toggleToc(){var tts="显示目录";var tth="隐藏目录";if(window.content_index_showTocToggle){window.content_index_showTocToggle=false;document.getElementById("content-index-contents").style.display="block";document.getElementById("content-index-togglelink").innerHTML=tth}else{window.content_index_showTocToggle=true;document.getElementById("content-index-contents").style.display="none";document.getElementById("content-index-togglelink").innerHTML=tts}}
</script>
<ul id="content-index-contents"><li class="content-index-level-1"><a href="http://www.yalewoo.com/binary_search.html#思想" title="思想"><em>1</em><span>思想</span></a></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/binary_search.html#函数原型" title="函数原型"><em>2</em><span>函数原型</span></a></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/binary_search.html#实现版本1" title="实现版本1"><em>3</em><span>实现版本1</span></a><ul class="children"><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#思想" title="思想"><em>3.1</em><span>思想</span></a></li><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#实现的流程是这样的：" title="实现的流程是这样的："><em>3.2</em><span>实现的流程是这样的：</span></a></li><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html# 复杂度分析" title=" 复杂度分析"><em>3.3</em><span> 复杂度分析</span></a></li></ul></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/binary_search.html#二分查找版本2" title="二分查找版本2"><em>4</em><span>二分查找版本2</span></a><ul class="children"><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#改进角度" title="改进角度"><em>4.1</em><span>改进角度</span></a></li><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#代码" title="代码"><em>4.2</em><span>代码</span></a></li><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#复杂度分析" title="复杂度分析"><em>4.3</em><span>复杂度分析</span></a></li></ul></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/binary_search.html#版本3" title="版本3"><em>5</em><span>版本3</span></a><ul class="children"><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#改进角度" title="改进角度"><em>5.1</em><span>改进角度</span></a></li><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#代码" title="代码"><em>5.2</em><span>代码</span></a></li><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#分析" title="分析"><em>5.3</em><span>分析</span></a></li></ul></li><li class="content-index-level-1"><a href="http://www.yalewoo.com/binary_search.html#细节" title="细节"><em>6</em><span>细节</span></a><ul class="children"><li class="content-index-level-2"><a href="http://www.yalewoo.com/binary_search.html#防止溢出" title="防止溢出"><em>6.1</em><span>防止溢出</span></a></li></ul></li></ul></div>
<p>二分查找是一个用于有序数组查找的常用算法。它的基本思想非常简单，以至于我们都会自认为已经掌握。但是，纸上得来终觉浅，当实际动手的时候，还是会发现许多问题。下面雅乐网整理了一下二分查找算法的实现。</p>
<h3 id="思想">思想</h3>
<p>先看看维基百科的说法：</p>
<blockquote><p>二分查找的搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则查找成功；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。</p></blockquote>
<p>其实这种思想是很简单的，以升序为例，每次比较中间元素，如果要查找的元素小于中间元素，那么就在中间元素左边找；如果大于中间元素呢，就在右边找。</p>
<h3 id="函数原型">函数原型</h3>
<p>int binarysearch1(int a[], int x, int low, int high)</p>
<p>它第一个参数是要查找的数组，第二个参数是要查找的值，三、四个参数是查找区间，前闭后开。也就是说包含a[low]不包含a[high]。为什么这样设置呢，这是考虑到C语言一贯的做法……而且这样如果查找到末尾可以直接传入数组元素个数。这个要特别注意以下，因为这关系到下面代码中是用<还是<= 是high=mid还是high=mid-1</p>
<p>他的返回值是查找到的元素在数组中的下标。</p>
<h3 id="实现版本1">实现版本1</h3>
<h4 id="思想">思想</h4>
<p>根据上面的思想，可以很容易的得到这样一个算法。</p>
<p>把数组整体分成三个部分</p>
<p>a[low]到a[mid]——包括a[low] 不包括a[mid] 区间 [low, mid)</p>
<p>a[mid]</p>
<p>a[mid]到a[high] ——不包括a[mid]和a[high] 区间 (mid, high)</p>
<p>将目标元素x和a[mid]作比较</p>
<p>1. x < a[mid] ——x存在于左侧区间a[low]到a[mid]</p>
<p>2. a[mid] < x ——x存在于右侧区间</p>
<p>3. x == a[mid] 已经找到 可以返回</p>
<h4 id="实现的流程是这样的：">实现的流程是这样的：</h4>
<p>传入参数low和high 现在low是第一个元素的下标，high是最后一个元素下标+1 。也就是说high其实是到了数组的末尾越界了。但其实我们并不对high位置进行写入操作，所以是没有什么问题的。</p>
<p>我们先定义一个mid 用来表示中间元素的秩。</p>
<div id="crayon-5a4ee59469db4524606404" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch1(int a[], int x, int low, int high)
{
int mid;
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469db4524606404-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469db4524606404-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469db4524606404-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469db4524606404-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469db4524606404-5">5</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469db4524606404-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch1</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469db4524606404-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469db4524606404-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469db4524606404-4"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a4ee59469db4524606404-5"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>下面通过一个循环，当当前区间有效的时候执行循环 每次循环开始时，我们把mid赋值为low和high的中点</p>
<div id="crayon-5a4ee59469dc5106188482" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch1(int a[], int x, int low, int high)
{
int mid;
while (low < high)
{
mid=(low+high)/2;
}
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-5">5</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-6">6</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-7">7</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-8">8</div><div class="crayon-num" data-line="crayon-5a4ee59469dc5106188482-9">9</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch1</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-4"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-5"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-6"><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-o">=</span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-o">+</span><span class="crayon-v">high</span><span class="crayon-sy">)</span><span class="crayon-o">/</span><span class="crayon-cn">2</span><span class="crayon-sy">;</span><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-7"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-8"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a4ee59469dc5106188482-9"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>因为循环的过程中我们会不断通过比较改变low或high的值，当low<high的时候，[low, high)是有效的。反过来，low=high [low, high)实际上不包含元素，因为这个区间是前闭后开的，low>high的情况更不包含元素了。所以这个循环执行的条件是low<high。不满足这个条件时，区间内不包含元素。</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930111355.png"><img class="alignnone size-full wp-image-825" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930111355.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20140930111355" width="656" height="295" /></a></p>
<noscript><img class="alignnone size-full wp-image-825" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930111355.png" alt="scrn20140930111355" width="656" height="295" /></a></p></noscript>
<p>我们可以先比较x和a[mid]的关系</p>
<p>如果x<a[mid]，那么就在左半边区间进行查找。那么high = mid还是mid+1呢？由于【low，high）区间右边是开区间，并不包含a[high]这个元素的，而x是<a[mid]的，显然a[mid]不应该包含在查找区间中。所以设置high=mid是合适的，接下来会在左边区间（绿色部分）[low, mid)查找。可以看到，这样得到的区间和最开始的区间是一致的，都不包含high处的元素。这也是这个算法的一个不变性。</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930115448.png"><img class="alignnone size-full wp-image-826" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930115448.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20140930115448" width="634" height="473" /></a><br />
<noscript><img class="alignnone size-full wp-image-826" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930115448.png" alt="scrn20140930115448" width="634" height="473" /></a><br /></noscript>
</p>
<div id="crayon-5a4ee59469dce013247753" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch1(int a[], int x, int low, int high)
{
int mid;
while (low < high)
{
mid = (low + high) / 2;
if (x < a[mid])
high = mid;
}
return -1;
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-5">5</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-6">6</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-7">7</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-8">8</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-9">9</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-10">10</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-11">11</div><div class="crayon-num" data-line="crayon-5a4ee59469dce013247753-12">12</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469dce013247753-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch1</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-4"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-5"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-6"><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">/</span><span class="crayon-h"> </span><span class="crayon-cn">2</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-7"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-8"><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-9"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-10"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-11"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dce013247753-12"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>然后，如果a[mid] < x 呢？就在右边区间查找。同样的，我们的有效区间是[low, high)。是包含了low的，那么low设置为mid还是mid+1呢？当然是mid+1了，因为这种情况下mid不可能等于x了，只需要在其右边查找 也就是在区间[mid+1,high]之间查找咯</p>
<p>所以我们设置这种情况 low= mid+1;</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930115603.png"><img class="alignnone size-full wp-image-827" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930115603.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20140930115603" width="696" height="437" /></a><br />
<noscript><img class="alignnone size-full wp-image-827" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930115603.png" alt="scrn20140930115603" width="696" height="437" /></a><br /></noscript>
</p>
<div id="crayon-5a4ee59469dd5320053188" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch1(int a[], int x, int low, int high)
{
int mid;
while (low < high)
{
mid = (low + high) / 2;
if (x < a[mid])
high = mid;
else if (a[mid] < x)
low = mid + 1;
}
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-5">5</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-6">6</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-7">7</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-8">8</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-9">9</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-10">10</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-11">11</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-12">12</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-13">13</div><div class="crayon-num" data-line="crayon-5a4ee59469dd5320053188-14">14</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch1</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-4"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-5"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-6"><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">/</span><span class="crayon-h"> </span><span class="crayon-cn">2</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-7"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-8"><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-9"><span class="crayon-h"> </span><span class="crayon-st">else</span><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-10"><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-cn">1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-11"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-12"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-13"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a4ee59469dd5320053188-14"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>可以看出，不管是向左边查找还是向右边查找，得到的区间都和最初的low到high性质一致。</p>
<p>当然，还有第三种情况，那就是x == a[mid]这种情况下直接返回即可。</p>
<div id="crayon-5a4ee59469ddc069873235" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch1(int a[], int x, int low, int high)
{
int mid;
while (low < high)
{
mid = (low + high) / 2;
if (x < a[mid])
high = mid;
else if (a[mid] < x)
low = mid + 1;
else
return mid;
}
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-5">5</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-6">6</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-7">7</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-8">8</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-9">9</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-10">10</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-11">11</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-12">12</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-13">13</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-14">14</div><div class="crayon-num" data-line="crayon-5a4ee59469ddc069873235-15">15</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch1</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-4"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-5"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-6"><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">/</span><span class="crayon-h"> </span><span class="crayon-cn">2</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-7"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-8"><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-9"><span class="crayon-h"> </span><span class="crayon-st">else</span><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-10"><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-cn">1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-11"><span class="crayon-h"> </span><span class="crayon-st">else</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-12"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-13"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-14"><span class="crayon-h"> </span></div><div class="crayon-line" id="crayon-5a4ee59469ddc069873235-15"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>当区间不合法的时候，退出循环，意味着没有找到，这是可以返回没有找到，用我们这里用-1表示。</p>
<p>这样这个二分查找函数就完整了</p>
<div id="crayon-5a4ee59469de2184876283" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch1(int a[], int x, int low, int high)
{
int mid;
while (low < high)
{
mid = (low + high) / 2;
if (x < a[mid])
high = mid;
else if (a[mid] < x)
low = mid + 1;
else
return mid;
}
return -1;
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-5">5</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-6">6</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-7">7</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-8">8</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-9">9</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-10">10</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-11">11</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-12">12</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-13">13</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-14">14</div><div class="crayon-num" data-line="crayon-5a4ee59469de2184876283-15">15</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469de2184876283-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch1</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-4"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-5"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-6"><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">/</span><span class="crayon-h"> </span><span class="crayon-cn">2</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-7"><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-8"><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-9"><span class="crayon-h"> </span><span class="crayon-st">else</span><span class="crayon-h"> </span><span class="crayon-st">if</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-10"><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-cn">1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-11"><span class="crayon-h"> </span><span class="crayon-st">else</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-12"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-13"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-14"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de2184876283-15"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p></p>
<h4 id=" 复杂度分析"> 复杂度分析</h4>
<p>这种算法，在最好的情况下一下子mid就是x，可以直接返回。</p>
<p>而平均情况下深入到左侧区间需要一次比较，而深入到右侧区间要进行两次比较，所以平均进行1.5次比较，时间复杂度为O（1.5log n）。</p>
<p>可以想到，向左侧深入需要比较的次数最少，可以通过mid不同取法来使左侧元素多一些，从这个角度改进就得到了Fibonacci查找，它仅仅改变mid的取法，不是每次取中点了。有兴趣的同学可以查找资料，通过这种改进中点取法的方法得到的最优时间复杂度约为(1.44log n)。</p>
<h3 id="二分查找版本2">二分查找版本2</h3>
<h4 id="改进角度">改进角度</h4>
<p>版本1中向右深入需要两次比较，我们可以变为1次比较。这样，区间由原来的三个[low,mid) [mid,mid] (mid, high)变为两个</p>
<p>[low, mid) [mid,high) 。</p>
<p>这种情况下需要在最后区间长度变为1的时候判断一下该元素是不是要查找的元素。</p>
<h4 id="代码">代码</h4>
<p></p>
<div id="crayon-5a4ee59469de9739641522" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch2(int a[], int x, int low, int high)
{
int mid;
while (high - low > 1)
{
mid = (low + high) / 2;
x < a[mid] ? high = mid : low = mid;
}
return (x == a[low]) ? low : -1;
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-5">5</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-6">6</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-7">7</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-8">8</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-9">9</div><div class="crayon-num" data-line="crayon-5a4ee59469de9739641522-10">10</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469de9739641522-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch2</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-4"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">high</span><span class="crayon-h"> </span><span class="crayon-o">-</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">></span><span class="crayon-h"> </span><span class="crayon-cn">1</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-5"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-6"><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">/</span><span class="crayon-h"> </span><span class="crayon-cn">2</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-7"><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-sy">?</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">:</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-8"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-9"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o">==</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">low</span><span class="crayon-sy">]</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-sy">?</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">:</span><span class="crayon-h"> </span><span class="crayon-o">-</span><span class="crayon-cn">1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469de9739641522-10"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>如果x<a[mid] 就到区间[low, mid)查找。</p>
<p>如果x>= a[mid] 就到区间[mid, high)查找。为什么包含mid呢，因为a[mid]可能等于x。</p>
<h4 id="复杂度分析">复杂度分析</h4>
<p>这个版本总体上比版本1要平衡。虽然它必须区间减为1才能判断是否找到，但总体上说每次深入一个区间只需要1次比较，因此平均性能比版本1要好。</p>
<h3 id="版本3">版本3</h3>
<h4 id="改进角度">改进角度</h4>
<p>上面两个版本，虽然实现了查找的功能，但是却只是一个功能，因为它没有良好的语义接口。</p>
<p>比如，有多个元素相同时，返回第一个还是最后一个？查找失败时，返回-1又有什么用呢？</p>
<p>如果配合插入操作，插入元素保持数组的有序，那么查找失败时也返回钙元素需要的插入位置会更好。元素重复时，返回最后一个，也有利于插入操作并且保持相同元素按照插入顺序。</p>
<p>这样插入一个元素只需要 insert （search（x）+1， x）就可以插入并保持有序</p>
<p>例如 数组 1 3 6 6 9</p>
<p>查找4 会返回1 查找6返回3 以便后面的插入操作。</p>
<h4 id="代码">代码</h4>
<p></p>
<div id="crayon-5a4ee59469df1215551619" class="crayon-syntax crayon-theme-classic crayon-font-consolas crayon-os-pc print-yes notranslate" data-settings=" minimize scroll-mouseover disable-anim wrap" style=" margin-top: 12px; margin-bottom: 12px; font-size: 20px !important; line-height: 30px !important;">
<div class="crayon-plain-wrap"><textarea class="crayon-plain print-no" data-settings="dblclick" readonly style="-moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4; font-size: 20px !important; line-height: 30px !important;">
int binarysearch3(int a[], int x, int low, int high)
{
int mid;
while (low < high)
{
mid = (low + high) / 2;
x < a[mid] ? high = mid : low = mid + 1;
}
return --low;
}</textarea></div>
<div class="crayon-main" style="">
<table class="crayon-table">
<tr class="crayon-row">
<td class="crayon-nums " data-settings="show">
<div class="crayon-nums-content" style="font-size: 20px !important; line-height: 30px !important;"><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-1">1</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-2">2</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-3">3</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-4">4</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-5">5</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-6">6</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-7">7</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-8">8</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-9">9</div><div class="crayon-num" data-line="crayon-5a4ee59469df1215551619-10">10</div></div>
</td>
<td class="crayon-code"><div class="crayon-pre" style="font-size: 20px !important; line-height: 30px !important; -moz-tab-size:4; -o-tab-size:4; -webkit-tab-size:4; tab-size:4;"><div class="crayon-line" id="crayon-5a4ee59469df1215551619-1"><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-e">binarysearch3</span><span class="crayon-sy">(</span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-sy">]</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-sy">,</span><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-2"><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-3"><span class="crayon-h"> </span><span class="crayon-t">int</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-4"><span class="crayon-h"> </span><span class="crayon-st">while</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-5"><span class="crayon-h"> </span><span class="crayon-sy">{</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-6"><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-sy">(</span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-sy">)</span><span class="crayon-h"> </span><span class="crayon-o">/</span><span class="crayon-h"> </span><span class="crayon-cn">2</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-7"><span class="crayon-h"> </span><span class="crayon-v">x</span><span class="crayon-h"> </span><span class="crayon-o"><</span><span class="crayon-h"> </span><span class="crayon-v">a</span><span class="crayon-sy">[</span><span class="crayon-v">mid</span><span class="crayon-sy">]</span><span class="crayon-h"> </span><span class="crayon-sy">?</span><span class="crayon-h"> </span><span class="crayon-v">high</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">:</span><span class="crayon-h"> </span><span class="crayon-v">low</span><span class="crayon-h"> </span><span class="crayon-o">=</span><span class="crayon-h"> </span><span class="crayon-v">mid</span><span class="crayon-h"> </span><span class="crayon-o">+</span><span class="crayon-h"> </span><span class="crayon-cn">1</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-8"><span class="crayon-h"> </span><span class="crayon-sy">}</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-9"><span class="crayon-h"> </span><span class="crayon-st">return</span><span class="crayon-h"> </span><span class="crayon-o">--</span><span class="crayon-v">low</span><span class="crayon-sy">;</span></div><div class="crayon-line" id="crayon-5a4ee59469df1215551619-10"><span class="crayon-sy">}</span></div></div></td>
</tr>
</table>
</div>
</div><p>它返回不大于x的最大元素的下标。</p>
<p>该算法过程中，不变性</p>
<p>[0, low) <= x < (high, n)</p>
<p>左边区间一直是<=x的。</p>
<p><a target="_blank" href="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930122953.png"><img class="alignnone size-full wp-image-829" data-original="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930122953.png" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/loading.gif" alt="scrn20140930122953" width="671" height="449" /></a></p>
<noscript><img class="alignnone size-full wp-image-829" src="http://7d9rd6.com1.z0.glb.clouddn.com/wp-content/uploads/2014/09/scrn20140930122953.png" alt="scrn20140930122953" width="671" height="449" /></a></p></noscript>
<p>循环结束时 low为大于x的元素里面的最小的，x-1就是不大于x的元素的最大的。</p>
<h4 id="分析">分析</h4>
<p>这个版本，从语义上和效率上，都是不错的。</p>
<h3 id="细节">细节</h3>
<h4 id="防止溢出">防止溢出</h4>
<p>mid=(low+high)/2</p>
<p>可以改为mid= low + (high – low)/2</p>
<p>为了防止low+high太大。。。</p>
</div>
</article>
<div class="social-main">
<div class="post-like">
<a href="javascript:;" data-action="ding" data-id="824" class="specsZan ">点赞 <span class="count">
0</span>
</a>
</div>
<div class="reward-button"><a href="http://www.yalewoo.com/denote" target="_blank">赏</a>
<span class="reward-code">
<span class="alipay-code"> <img class="alipay-img wdp-appear" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/alipay.png"><b>支付宝打赏</b> </span> <span class="wechat-code"> <img class="wechat-img wdp-appear" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/img/wechatpay.png"><b>微信打赏</b> </span>
</span>
</div>
<div class="post-like">
<a id="fenxianganniu" onClick="show_bdsharebox();">分享
</a>
</div>
<div class="bdsharebuttonbox" id="bdsharebuttonbox">
</div>
</div>
<div class="reward-notice">
<p class="">如果文章对你有帮助，欢迎点赞或打赏（金额不限）。你的打赏将全部用于支付网站服务器费用和提高网站文章质量，谢谢支持。</p>
</div>
<div class="article-copyright">
<b> 版权声明: </b>
<p> 本文由 <a href="http://www.yalewoo.com/author/yalewoo" title="由yalewoo发布" rel="author">yalewoo</a> 原创，商业转载请联系作者获得授权。 <br>非商业转载请注明作者 <a href="http://www.yalewoo.com/author/yalewoo" title="由yalewoo发布" rel="author">yalewoo</a> 或 <a href="http://www.yalewoo.com/" title="雅乐网" ?>雅乐网</a> ，并附带本文链接：<br><a href="http://www.yalewoo.com/binary_search.html" title=详解二分查找算法>http://www.yalewoo.com/binary_search.html</a></p>
</div>
<div class="post-navigation">
<div class="post-previous">
<p>上一篇：</p>
<a href="http://www.yalewoo.com/chromeos_apk.html" rel="prev">linux可以开始运行apk了</a> </div>
<div class="post-next">
<p>下一篇：</p>
<a href="http://www.yalewoo.com/bubble_sort.html" rel="next">冒泡排序：思路、详解、C语言实现</a> </div>
</div>
<div class="related_posts">
<p>与 <a href="http://www.yalewoo.com/tag/%e6%9f%a5%e6%89%be" rel="tag">查找</a>, <a href="http://www.yalewoo.com/tag/%e7%ae%97%e6%b3%95" rel="tag">算法</a> 相关的文章</p>
<ul>
<li><a rel="bookmark" href="http://www.yalewoo.com/oj_bineary_search_and_rotate_array_search.html" title="【OJ】二分查找、旋转数组查找、二分查找变种" target="_blank">【OJ】二分查找、旋转数组查找、二分查找变种</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/quickselect_and_linearselect.html" title="选取算法：中位数和第k小数" target="_blank">选取算法：中位数和第k小数</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/counting_sort_and_radix_sort.html" title="计数排序和基数排序" target="_blank">计数排序和基数排序</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/sort_decision_tree.html" title="基于比较的排序算法的下界" target="_blank">基于比较的排序算法的下界</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/heap_and_heapsort.html" title="堆和堆排序" target="_blank">堆和堆排序</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/in_triangle_test.html" title="向量叉积和应用：判断点是否在三角形内部" target="_blank">向量叉积和应用：判断点是否在三角形内部</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/queue_findmax.html" title="用两个栈模拟队列，快速获得队列的最大值" target="_blank">用两个栈模拟队列，快速获得队列的最大值</a></li>
<li><a rel="bookmark" href="http://www.yalewoo.com/master_theorem.html" title="使用主定理求解递归式" target="_blank">使用主定理求解递归式</a></li>
</ul>
</div>
<div class="comments-template">
<div id="comments" class="comments-area">
<div id="respond" class="comment-respond">
<h3 id="reply-title" class="comment-reply-title">我要评论 <small><a rel="nofollow" id="cancel-comment-reply-link" href="/binary_search.html#respond" style="display:none;">取消回复</a></small></h3> <form action="http://www.yalewoo.com/wp-comments-post.php" method="post" id="commentform" class="comment-form">
<p class="comment-form-comment"><textarea id="comment" name="comment" cols="45" rows="8" maxlength="65525" aria-required="true" required="required"></textarea></p>
<script type="text/javascript" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/show_smilies.js"></script>
<div class="ylw_comment_toolbar">
<a class="button-insert-smilies" id="button-insert-smilies" title="插入表情" onClick="show_smilies();"></a>
</div>
<div class="ylw_smilies_box_wrapper">
<div class="ylw_smilies_box" id="ylw_smilies_box">
</div>
</div><div class="comment-name-email-url"><p class="comment-form-author"><label for="author">姓名</label><input id="author" name="author" type="text" value="" size="30" /> </p>
<p class="comment-form-email"><label for="email">邮箱</label><input id="email" name="email" type="text" value="" size="30" /> </p>
<p class="comment-form-url"><label for="url">网址</label><input id="url" name="url" type="text" value="" size="30" /></p></div><div class='comment_yzm'>验证码*： 4 + 1 = <input type='text' name='sum' class='math_textfield' required='required' value='' size='25' tabindex='4'><input type='hidden' name='num1' value='4'><input type='hidden' name='num2' value='1'></div><div class="comment-right"><div class="comment-submit-button">
<p class="form-submit"><input name="submit" type="submit" id="submit" class="submit" value="发表评论" /> <input type='hidden' name='comment_post_ID' value='824' id='comment_post_ID' />
<input type='hidden' name='comment_parent' id='comment_parent' value='0' />
</p></div><div class="ylw_comment_notifyme"><input type="checkbox" name="comment_mail_notify" id="comment_mail_notify" value="comment_mail_notify" checked="checked" style="margin-left:20px;" /><label for="comment_mail_notify">有人回复时邮件通知我</label></div></div></div><div class="clear"></div> </form>
</div><!-- #respond -->
</div><!-- .comments-area -->
</div>
</section>
</div>
<footer id="footer">
Copyright © <a title="雅乐网" href="http://www.yalewoo.com">雅乐网</a> /<a title="自豪地采用WordPress" href="https://cn.wordpress.org" target="_blank">WordPress</a> / <a title="YLW3.0主题" href="http://www.yalewoo.com/ylw3.html" target="_blank">YLW3.0</a> / <a title="老薛主机" href="https://my.laoxuehost.net/aff.php?aff=2518" target="_blank">老薛主机</a> / <a title="七牛云存储" href="https://portal.qiniu.com/signup?code=3li1yeb2ph1ea" target="_black">七牛云存储</a>
<div id="footer_menu">
<div class="menu-%e5%ba%95%e9%83%a8-container"><ul id="menu-%e5%ba%95%e9%83%a8" class="menu"><li id="menu-item-655" class="menu-item menu-item-type-custom menu-item-object-custom menu-item-655"><a target="_blank" href="http://www.yalewoo.com/sitemap.xml">站点地图</a></li>
</ul></div> </div>
<div id="cnzztongji">
<script type="text/javascript">var cnzz_protocol = (("https:" == document.location.protocol) ? " https://" : " http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1252889774'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s5.cnzz.com/stat.php%3Fid%3D1252889774%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));</script>
<script>
var _hmt = _hmt || [];
(function() {
var hm = document.createElement("script");
hm.src = "//hm.baidu.com/hm.js?e937132d7f7e86dfb5300ce1ab2c25f7";
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(hm, s);
})();
</script>
</div>
</footer>
<script type="text/javascript" src="http://www.yalewoo.com/wp-content/themes/YLW3_lite/js/backtop.js"></script>
<script type='text/javascript' src='http://www.yalewoo.com/wp-includes/js/comment-reply.min.js?ver=4.7.8'></script>
</body>
</html>
<!-- Dynamic page generated in 1.296 seconds. -->
<!-- Cached page generated by WP-Super-Cache on 2018-01-05 10:40:20 -->
<!-- Compression = gzip -->
<!-- super cache -->