电脑/python/算法/算法入门之查找篇.html

<!DOCTYPE html>
<html>
<head>
<!-- 2016-07-30 六 23:04 -->
<meta  charset="utf-8">
<meta  name="viewport" content="width=device-width, initial-scale=1">
<title>算法入门之查找篇</title>
<meta  name="generator" content="Org-mode">
<meta  name="author" content="万泽(德山书生)">
<meta  name="description" content="制作者邮箱：a358003542@gmail.com"
>
<style type="text/css">
body {
    margin-right: auto;
    margin-left: auto;
}

.title {
    display: block;
    text-align: center;
    padding: 10px;
}

.center-block {
    display: block;
    margin-left: auto;
    margin-right: auto;
}

.underline{
    text-decoration: underline;
}
   html, body {
    margin: 0;
    padding: 0;
    font-family:"Microsoft YaHei",Arial,Helvetica,sans-serif,"宋体";
    font-size: 1em;
}

#content {
    display: block;
    margin-left: auto;
    margin-right: auto;
    background:#fcfcfc;
    height:100%;
    margin-left:300px;
    max-width:800px;
    min-height:100%;
    padding:1.618em 3.236em;
}

code {
    padding: 2px 4px;
    color: #c7254e;
    background-color: #f9f2f4;
    border-radius: 4px;
}

pre {
    max-width: 100%;
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
    overflow : auto;
}


blockquote {
    padding: 10px 20px;
    margin: 0 0 20px;
    font-size: 17.5px;
    border-left: 5px solid #eee;
}

li{
    margin-top: 0.5em;
    margin-bottom: 0.5em;
}

p{
    text-indent:2em;
    line-height:150%;
}

/* dl */
dl {
    margin-top: 0;
    margin-bottom: 20px;
}
dt {
    font-weight: 700;
    line-height: 150%;
    margin-top: 0.5em;
    margin-bottom: 0.5em;
}
dd {
    line-height: 150%;
}

@media (min-width: 768px) {
  dt {
    white-space: nowrap;
  }
}

video{
    max-width: 100%;
    margin-left: auto;
    margin-right: auto;
}

figure p{
    text-indent:0em;
}
img{
    max-width: 100%;
}

embed{
    max-width: 100%;
    margin-left: auto;
    margin-right: auto;
}

figure{
    text-align: center;
}

/*  class  */
.FRAMED{
    max-width:100%;
    border:1px solid ;
    padding: 1em;
    -webkit-box-sizing: border-box;
    -moz-box-sizing: border-box;
    box-sizing: border-box;
}

.NOTECARD{
    width: 35%;
    position:relative;
    right: -30%;
    padding: 1em;
    margin:0 auto;
    border: solid 1px;
    -webkit-box-sizing: border-box;
    -moz-box-sizing: border-box;
    box-sizing: border-box;
}

/*
table
*/
table {
    border-collapse: collapse;
    border-spacing: 0;
    margin: 16px 0;
    empty-cells: show;
    border: 1px solid #ccc;
    width: 100%;
    display: table;
}

table tr {
    border-bottom: 1px solid #ddd;
}
table th,table td{
    padding:8px;
}

table tr:nth-child(even) {
    background-color: #f1f1f1;
}


ul,ol,dl{
    line-height:24px;
    list-style-image:none;
    /* list-style:none; */
    margin:0px 0px 24px 0px;
    padding:0;
}

li{
    margin-left: 24px;
}

dd{
    margin:0;
}

#content .section ul,#content .toctree-wrapper ul,article ul{
    list-style:disc;
    line-height:24px;
    margin-bottom:24px}

#content .section ul li,#content .toctree-wrapper ul li,article ul li{
    list-style:disc;
    margin-left:24px}

#content .section ul li p:last-child,#content .toctree-wrapper ul li p:last-child,article ul li p:last-child{
                                                                                                                                  margin-bottom:0}

#content .section ul li ul,#content .toctree-wrapper ul li ul,article ul li ul{
    margin-bottom:0}

#content .section ul li li,#content .toctree-wrapper ul li li,article ul li li{
    list-style:circle}

#content .section ul li li li,#content .toctree-wrapper ul li li li,article ul li li li{
    list-style:square}

#content .section ul li ol li,#content .toctree-wrapper ul li ol li,article ul li ol li{
    list-style:decimal}

#content .section ol,#content ol,article ol{
    list-style:decimal;
    line-height:24px;
    margin-bottom:24px}

#content .section ol li,#content ol li,article ol li{
    list-style:decimal;
    margin-left:24px}

#content .section ol li p:last-child,#content ol li p:last-child,article ol li p:last-child{
                                                                                                                           margin-bottom:0}

#content .section ol li ul,#content ol li ul,article ol li ul{
    margin-bottom:0}

#content .section ol li ul li,#content ol li ul li,article ol li ul li{
    list-style:disc}

dl dt{
    font-weight:bold;
}

dl p,dl table,dl ul,dl ol{
    margin-bottom:12px !important;
}

dl dd{
    margin:0 0 12px 24px;
}

@media print{
    .codeblock,pre.src{
        white-space:pre.src-wrap}
}

@media print{
    html,body,section{
        background:none !important}

    *{
        box-shadow:none !important;
        text-shadow:none !important;
        filter:none !important;
        -ms-filter:none !important}

    a,a:visited{
          text-decoration:underline}

    pre.src,blockquote{
        page-break-inside:avoid}

    thead{
        display:table-header-group}

    tr,img{
        page-break-inside:avoid}

    img{
        max-width:100% !important}

    @page{
        margin:0.5cm}

    p,h2,h3{
        orphans:3;
        widows:3}

    h2,h3{
        page-break-after:avoid}
}

@media print{
    #postamble{
        display:none}

    #content{
        margin-left:0}
}

@media print{
    #table-of-contents{
        display:none}

    @page{
        size: auto;
        margin: 25mm 25mm 25mm 25mm;}

    body {
        margin: 0px;}
}

@media screen and (max-width: 768px){
}

@media only screen and (max-width: 480px){
}

@media screen and (max-width: 768px){
    .tablet-hide{
        display:none}
}

@media screen and (max-width: 480px){
    .mobile-hide{
        display:none}
}

@media screen and (max-width: 480px){
}

@media screen and (max-width: 768px){
    #content{
        margin-left:0;
        padding: 1em 1em;}

    #content #content{
        padding:1.618em}

    #content.shift{
        position:fixed;
        min-width:100%;
        left:85%;
        top:0;
        height:100%;
        overflow:hidden}
}

@media screen and (min-width: 1400px){
    #content{
        background:rgba(0,0,0,0.05)}

    #content{
        background:#fcfcfc}
}

@media screen and (max-width: 768px){
    #copyright{
        width:85%;
        display:none}

    #copyright.shift{
        display:block}

    img{
        width:100%;
        height:auto}
}

@media screen and (max-width: 480px){
    #content .sidebar{
        width:100%}
}


.figure p{
    color:#000;
    font:italic 85%/1 arial,sans-serif;
    padding:1em 0;
}

.rotate-90{
    -webkit-transform:rotate(90deg);
    -moz-transform:rotate(90deg);
    -ms-transform:rotate(90deg);
    -o-transform:rotate(90deg);
    transform:rotate(90deg);
}

.rotate-270{
    -webkit-transform:rotate(270deg);
    -moz-transform:rotate(270deg);
    -ms-transform:rotate(270deg);
    -o-transform:rotate(270deg);
    transform:rotate(270deg);
}

#toggle-sidebar,
#table-of-contents .close-sidebar {
    display: none;
}

@media screen and (max-width: 768px) {
    #table-of-contents {
        display: none;
        width: 60%;
    }

    #table-of-contents h2 a {
        display: block;
    }

    #table-of-contents:target {
        display: block;
    }

    #copyright, #postamble {
        display: none;
    }

    #toggle-sidebar {
        background-color: #2980B9;
        display: block;
        margin-bottom: 1.6em;
        padding: 0.6em;
        text-align: center;
    }

    #toggle-sidebar h2 {
        color: white;
        font-size: 100%;
        line-height: 50px;
        margin: 0;
        padding: 0;
    }

    #table-of-contents .close-sidebar {
       color: rgba(255, 255, 255, 0.3);
       display: inline-block;
       margin: 0px 10px 0px 45px;
       padding: 10px;
    }
}

*{
    -webkit-box-sizing:border-box;
    -moz-box-sizing:border-box;
    box-sizing:border-box;
}

figcaption,figure,footer,header,hgroup,nav{
    display:block}

ins{
    background:#ff9;
    color:#000;
    text-decoration:none}

mark{
    background:#ff0;
    color:#000;
    font-style:italic;
    font-weight:bold}

small{
    font-size:85%}

sub,sup{
    font-size:75%;
    line-height:0;
    position:relative;
    vertical-align:baseline}

sup{
    top:-0.5em}

sub{
    bottom:-0.25em}

img{
    -ms-interpolation-mode:bicubic;
    vertical-align:middle;
    max-width:100%}

svg:not(:root){
    overflow:hidden}

figure{
    margin:0}

label{
    cursor:pointer}

legend{
    border:0;
    margin-left:-7px;
    padding:0;
    white-space:normal}

#content .danger,#content .error{
    background:#fdf3f2}

legend{
    display:block;
    width:100%;
    border:0;
    padding:0;
    white-space:normal;
    margin-bottom:24px;
    font-size:150%;
    *margin-left:-7px}

label{
    display:block;
    margin:0 0 0.3125em 0;
    color:#333;
    font-size:90%}

a{
    color:#2980B9;
    text-decoration:none;
    cursor:pointer}


a:hover,a:active{
    outline:0;
}

a:hover{
    color:#3091d1}

a:visited{
    color:#9B59B6}

.left{
    text-align:left}

.center{
    text-align:center}

.right{
    text-align:right}

hr{
    display:block;
    height:1px;
    border:0;
    border-top:1px solid #e1e4e5;
    margin:24px 0;
    padding:0}

#table-of-contents li{
    list-style:none;
    margin-left: 0px;
}

#table-of-contents header{
    height:32px;
    display:inline-block;
    line-height:32px;
    padding:0 1.618em;
    display:block;
    font-weight:bold;
    text-transform:uppercase;
    font-size:80%;
    color:#2980B9;
    white-space:nowrap}

#table-of-contents ul{
    margin-bottom:0}

#table-of-contents li.divide-top{
    border-top:solid 1px #404040}

#table-of-contents li.divide-bottom{
    border-bottom:solid 1px #404040}

#table-of-contents li.current{
    background:#e3e3e3}

#table-of-contents li.current a{
    color:gray;
    border-right:solid 1px #c9c9c9;
    padding:0.4045em 2.427em}

#table-of-contents li.current a:hover{
    background:#d6d6d6}

#table-of-contents li a{
    /* color:#404040; */
    padding:0.4045em 1.618em;
    position:relative;
    /* background:#fcfcfc; */
    border:none;
    /* border-bottom:solid 1px #c9c9c9; */
    /* border-top:solid 1px #c9c9c9; */
    padding-left:1.618em -4px}

#table-of-contents li.on a:hover,#table-of-contents li.current>a:hover{
    background:#fcfcfc}

#table-of-contents li ul li a{
    /* background:#c9c9c9; */
    padding:0.4045em 2.427em}

#table-of-contents li ul li ul li a{
    padding:0.4045em 3.236em}

#table-of-contents li.current ul{
    display:block}

/* #table-of-contents li ul{ */
/*     margin-bottom:0; */
/*     display:none} */

#table-of-contents .local-toc li ul{
    display:block}

#table-of-contents li ul li a{
    margin-bottom:0;
    color:#b3b3b3;
    font-weight:normal}

#table-of-contents a{
    display:inline-block;
    line-height:18px;
    padding:0.4045em 1.618em;
    display:block;
    position:relative;
    font-size:90%;
    color:#b3b3b3;
    direction: ltr;
}

#table-of-contents a:hover{
    background-color:#4e4a4a;
    cursor:pointer}

/* #text-table-of-contents { */
/*     overflow:scroll; */
/* } */

#table-of-contents{
    position:fixed;
    top:0;
    left:0;
    width:300px;
    overflow-x:hidden;
    overflow-y:scroll;
    height:100%;
    background:#343131;
    z-index:200;
    scrollbar-base-color: #1F1D1D;
    scrollbar-arrow-color: #b3b3b3;
    scrollbar-shadow-color: #1F1D1D;
    scrollbar-track-color : #343131;
}

#table-of-contents h2{
    z-index:200;
    background-color:#2980B9;
    text-align:center;
    padding:0.809em;
    display:block;
    color:#fcfcfc;
    font-size: 100%;
    margin-bottom:0.809em}

ul.nav li ul li {
    display: none;
}

ul.nav li ul li ul li {
    display: none;
}

ul.nav li.active ul li {
    display: inline;
}

ul.nav li.active ul li ul li {
    display: inline;
}

ul.nav li.active ul li a {
    background-color: #E3E3E3;
    color: #8099B0;
    border-right:solid 1px #c9c9c9 !important;
}

ul.nav li.active ul li.active a {
    background-color: #C9C9C9;
    color: black !important;
    font-weight: bold !important;
}

ul.nav li.active ul li.active ul li.active a {
    color: black !important;
    font-weight: bold !important;
    display: block !important;
}

ul.nav li.active ul li.active ul li a {
    color: #808080 !important;
    font-weight: normal !important;
    display: block !important;
}

ul.nav li.active ul li ul li a {
    display: none !important;
}


ul.nav li ul li ul li ul li {
    display: none !important; /* as long as nav is on multiple levels of ul */
    /* display: none; /* as long as nav is on multiple levels of ul *\/ */
}

ul.nav li.active > a {
    border-bottom:solid 1px #c9c9c9 !important; /* XXX Restrict it to 2nd level */
    border-right:solid 1px #c9c9c9 !important;
}

ul.nav li.active a {
    color: gray !important;
    font-weight:bold;
    background-color: white;
    border-right:solid 0px white !important;
}

ul.nav > li.active > a {
    color: black !important;
}

footer{
    color:#999}

footer p{
    margin-bottom:12px}

#copyright, #postamble{
    position:fixed;
    bottom:0;
    left:0;
    width:300px;
    color:#fcfcfc;
    background:#1f1d1d;
    border-top:solid 10px #343131;
    font-family:"Lato","proxima-nova","Helvetica Neue",Arial,sans-serif;
    font-size: 90%;
    z-index:400;
    padding:12px;
}

#postamble .author {
    font-size: 100%;
    margin-bottom: 0px;
}

#postamble .date {
    font-size: 90%;
    margin-bottom: 0px;
    color: #27AE60;
}

#postamble .creator,#postamble .validation {
    display:none;
}

#copyright a{
    color:#2980B9;
    text-decoration:none}

#copyright .rst-current-version{
    padding:12px;
    background-color:#272525;
    display:block;
    text-align:right;
    font-size:90%;
    cursor:pointer;
    color:#27AE60;
    *zoom:1}

#content img{
    max-width:100%;
    height:auto !important}

#content div.figure{
    margin-bottom:24px}

#content div.figure.align-center{
    text-align:center}

#content .section>img,#content .section>a>img{
    margin-bottom:24px}

.verse{
    border-left:5px solid #6AB0DE;
    background-color: #E7F2FA;
    padding: 6px 20px;
    font-style:italic;
}

#content .note .last,#content .attention .last,#content .caution .last,#content .danger .last,#content .error .last,#content .hint .last,#content .important .last,#content .tip .last,#content .warning .last,#content .seealso .last,#content .admonitiontodo .last{
    margin-bottom:0}

#content .admonition-title:before{
    margin-right:4px}

#content .section ol p,#content .section ul p{
    margin-bottom:12px}

#content h1 .headerlink,#content h2 .headerlink,#content h3 .headerlink,#content h4 .headerlink,#content h5 .headerlink,#content h6 .headerlink,#content dl dt .headerlink{
    display:none;
    visibility:hidden;
    font-size:14px}

#content h1 .headerlink:after,#content h2 .headerlink:after,#content h3 .headerlink:after,#content h4 .headerlink:after,#content h5 .headerlink:after,#content h6 .headerlink:after,#content dl dt .headerlink:after{
    visibility:visible;
    content:"";
    font-family:FontAwesome;
    display:inline-block}

#content h1:hover .headerlink,#content h2:hover .headerlink,#content h3:hover .headerlink,#content h4:hover .headerlink,#content h5:hover .headerlink,#content h6:hover .headerlink,#content dl dt:hover .headerlink{
    display:inline-block}

#content .sidebar{
    float:right;
    width:40%;
    display:block;
    margin:0 0 24px 24px;
    padding:24px;
    background:#f3f6f6;
    border:solid 1px #e1e4e5}

#content .sidebar p,#content .sidebar ul,#content .sidebar dl{
    font-size:90%}

#content .sidebar .last{
    margin-bottom:0}

#content .sidebar .sidebar-title{
    display:block;
    font-family:"Roboto Slab","ff-tisa-web-pro","Georgia",Arial,sans-serif;
    font-weight:bold;
    background:#e1e4e5;
    padding:6px 12px;
    margin:-24px;
    margin-bottom:24px;
    font-size:100%}

#content .footnote-reference,#content .citation-reference{
    vertical-align:super;
    font-size:90%}

span[id*='MathJax-Span']{
    color:#404040}

.math{
    text-align:center}

#footnotes{
    border-top:1px solid #e1e4e5;
    padding-top: 36px;
}

h2.footnotes{
    display:none;
}


.footnum:before, .footref:before{
    content:"[";
}

.footnum:after, .footref:after{
    content:"]";
}

.footpara {
    color: #999;
    font-size: 90%;
    font-family:"Lato","proxima-nova","Helvetica Neue",Arial,sans-serif;
    padding-bottom: 8px;
    padding-left: 16px;
    padding-right: 16px;
    padding-top: 8px;
    line-height: 1.25em;
    /* display: inline; */
}
.highlight .hll { background-color: #ffffcc }
.highlight  { background: #f8f8f8; }
.highlight .c { color: #8f5902; font-style: italic } /* Comment */
.highlight .err { color: #a40000; border: 1px solid #ef2929 } /* Error */
.highlight .g { color: #000000 } /* Generic */
.highlight .k { color: #204a87; font-weight: bold } /* Keyword */
.highlight .l { color: #000000 } /* Literal */
.highlight .n { color: #000000 } /* Name */
.highlight .o { color: #ce5c00; font-weight: bold } /* Operator */
.highlight .x { color: #000000 } /* Other */
.highlight .p { color: #000000; font-weight: bold } /* Punctuation */
.highlight .ch { color: #8f5902; font-style: italic } /* Comment.Hashbang */
.highlight .cm { color: #8f5902; font-style: italic } /* Comment.Multiline */
.highlight .cp { color: #8f5902; font-style: italic } /* Comment.Preproc */
.highlight .cpf { color: #8f5902; font-style: italic } /* Comment.PreprocFile */
.highlight .c1 { color: #8f5902; font-style: italic } /* Comment.Single */
.highlight .cs { color: #8f5902; font-style: italic } /* Comment.Special */
.highlight .gd { color: #a40000 } /* Generic.Deleted */
.highlight .ge { color: #000000; font-style: italic } /* Generic.Emph */
.highlight .gr { color: #ef2929 } /* Generic.Error */
.highlight .gh { color: #000080; font-weight: bold } /* Generic.Heading */
.highlight .gi { color: #00A000 } /* Generic.Inserted */
.highlight .go { color: #000000; font-style: italic } /* Generic.Output */
.highlight .gp { color: #8f5902 } /* Generic.Prompt */
.highlight .gs { color: #000000; font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #800080; font-weight: bold } /* Generic.Subheading */
.highlight .gt { color: #a40000; font-weight: bold } /* Generic.Traceback */
.highlight .kc { color: #204a87; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #204a87; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #204a87; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #204a87; font-weight: bold } /* Keyword.Pseudo */
.highlight .kr { color: #204a87; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #204a87; font-weight: bold } /* Keyword.Type */
.highlight .ld { color: #000000 } /* Literal.Date */
.highlight .m { color: #0000cf; font-weight: bold } /* Literal.Number */
.highlight .s { color: #4e9a06 } /* Literal.String */
.highlight .na { color: #c4a000 } /* Name.Attribute */
.highlight .nb { color: #204a87 } /* Name.Builtin */
.highlight .nc { color: #000000 } /* Name.Class */
.highlight .no { color: #000000 } /* Name.Constant */
.highlight .nd { color: #5c35cc; font-weight: bold } /* Name.Decorator */
.highlight .ni { color: #ce5c00 } /* Name.Entity */
.highlight .ne { color: #cc0000; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #000000 } /* Name.Function */
.highlight .nl { color: #f57900 } /* Name.Label */
.highlight .nn { color: #000000 } /* Name.Namespace */
.highlight .nx { color: #000000 } /* Name.Other */
.highlight .py { color: #000000 } /* Name.Property */
.highlight .nt { color: #204a87; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #000000 } /* Name.Variable */
.highlight .ow { color: #204a87; font-weight: bold } /* Operator.Word */
.highlight .w { color: #f8f8f8; text-decoration: underline } /* Text.Whitespace */
.highlight .mb { color: #0000cf; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000cf; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000cf; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000cf; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000cf; font-weight: bold } /* Literal.Number.Oct */
.highlight .sb { color: #4e9a06 } /* Literal.String.Backtick */
.highlight .sc { color: #4e9a06 } /* Literal.String.Char */
.highlight .sd { color: #8f5902; font-style: italic } /* Literal.String.Doc */
.highlight .s2 { color: #4e9a06 } /* Literal.String.Double */
.highlight .se { color: #4e9a06 } /* Literal.String.Escape */
.highlight .sh { color: #4e9a06 } /* Literal.String.Heredoc */
.highlight .si { color: #4e9a06 } /* Literal.String.Interpol */
.highlight .sx { color: #4e9a06 } /* Literal.String.Other */
.highlight .sr { color: #4e9a06 } /* Literal.String.Regex */
.highlight .s1 { color: #4e9a06 } /* Literal.String.Single */
.highlight .ss { color: #4e9a06 } /* Literal.String.Symbol */
.highlight .bp { color: #3465a4 } /* Name.Builtin.Pseudo */
.highlight .vc { color: #000000 } /* Name.Variable.Class */
.highlight .vg { color: #000000 } /* Name.Variable.Global */
.highlight .vi { color: #000000 } /* Name.Variable.Instance */
.highlight .il { color: #0000cf; font-weight: bold } /* Literal.Number.Integer.Long */
</style>
</head>
<body>
<div id="content">
<header>
<h1 class="title">算法入门之查找篇</h1>
</header><nav id="table-of-contents">
<h2>Table of Contents</h2>
<div id="text-table-of-contents">
<ul>
<li><a href="#orgheadline3">1. 二分查找</a>
<ul>
<li><a href="#orgheadline1">1.1. 抽象的二分查找思想讨论</a></li>
<li><a href="#orgheadline2">1.2. binsect模块</a></li>
</ul>
</li>
</ul>
</div>
</nav>


<div class="outline-2">
<h2 id="orgheadline3">二分查找</h2>
<div class="outline-text-2" id="text-1">
<p>
二分查找以前也接触过吧，当时不怎么重视，认为就是一种快速查找方法了，参看 <a href="https://github.com/qiwsir/algorithm/blob/master/bin_search.md">这个网页</a> ，其认为python的 <code>index</code> 方法并不是使用的二分查找，所以对大规模查询会很吃力。考虑到python一般的sequence对象都没有预排序，所以这种说法可信度还是很高的。然后利用python的 <code>bisect</code> 模块，我们可以构建出一种预排序的支持更快查询的接口，其内部就是使用的二分查找。
</p>

<p>
关于二分查找的原理我就不啰嗦了，这里我想说的是，最近在看MIT的那个视频（就是MIT的那个有名的视频），其中第三课讲到了利用二分查找的思想来求解平方根的问题，这个对我启发很大。尤其是那一句: 任何计算机问题如果找不到好的方法，实际上都可以穷举而得，而穷举的过程，我们不需要一个个都试一下，我们只需要将这些可能的结果集排序之后，进行二分查找来快速缩小可能的结果集，那么我们就可以逐步更快地趋近理想结果了。
</p>

<p>
这使得我认识到，二分查找思想的应用可不限于查找，而是更普遍，可以看作一种有关计算机的最核心的最底层的那种计算思想的东西。所以本小节关于二分查找主要分为两个内容，一是关于查找部分，主要集中讨论了python bisect模块；一是以一种更加抽象的思维来描述二分查找思想。
</p>
</div>

<div class="outline-3">
<h3 id="orgheadline1">抽象的二分查找思想讨论</h3>
<div class="outline-text-3" id="text-1-1">
<p>
现在我们将可能的结果集认为是某个函数f(x)的输入参数，然后我们有目标参数target，令f(x)=target的时候我们说我们就找到了目标结果x，或者说目标x符合函数f(x)=target这个关系。然后假设我们的考察对象f(x)在目标结果集内存在简单的增减关系，即目标集合可以由此排序，那么我们就可以开展二分查找来找到目标结果x了。
</p>

<p>
以相等查找为例，f(x)函数即f(x)=x，也就是输入什么同样输出的是什么。如果x=target，则我们说目标x复合条件f(x)=target，则该x就是我们要找的目标结果x。
</p>

<p>
如果我们定义f(x)=x*x，则意思是我们要找某个x符合条件 x*x=target，这就是求平方根的过程。
</p>

<p>
程序主体 <code>binary_search</code> 函数大体是这样的，主要参考了algorithms模块binary_search.py文件，然后稍作修改。
</p>

<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">binary_search</span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="n">seq</span><span class="p">,</span><span class="n">target</span><span class="p">):</span>
    <span class="n">low</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="n">high</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">seq</span><span class="p">)</span><span class="o">-</span><span class="mi">1</span>

    <span class="k">while</span> <span class="n">high</span> <span class="o">&gt;=</span> <span class="n">low</span><span class="p">:</span>
        <span class="n">mid</span> <span class="o">=</span> <span class="n">low</span> <span class="o">+</span> <span class="p">(</span><span class="n">high</span> <span class="o">-</span> <span class="n">low</span><span class="p">)</span> <span class="o">//</span> <span class="mi">2</span>
        <span class="k">print</span><span class="p">(</span><span class="n">low</span><span class="p">,</span><span class="n">high</span><span class="p">,</span><span class="n">mid</span><span class="p">)</span>
        <span class="k">if</span> <span class="n">f</span><span class="p">(</span><span class="n">seq</span><span class="p">[</span><span class="n">mid</span><span class="p">])</span> <span class="o">&lt;</span> <span class="n">target</span><span class="p">:</span> <span class="c1">##higher area</span>
            <span class="n">low</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">+</span> <span class="mi">1</span>
        <span class="k">elif</span> <span class="n">f</span><span class="p">(</span><span class="n">seq</span><span class="p">[</span><span class="n">mid</span><span class="p">])</span> <span class="o">&gt;</span> <span class="n">target</span><span class="p">:</span><span class="c1">##lower area</span>
            <span class="n">high</span> <span class="o">=</span> <span class="n">mid</span> <span class="o">-</span> <span class="mi">1</span>
        <span class="k">else</span><span class="p">:</span>
            <span class="k">print</span><span class="p">(</span><span class="s1">&#39;exactly&#39;</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">seq</span><span class="p">[</span><span class="n">mid</span><span class="p">]</span>
    <span class="k">else</span><span class="p">:</span>
        <span class="k">print</span><span class="p">(</span><span class="s1">&#39;nearly&#39;</span><span class="p">)</span>
        <span class="k">return</span> <span class="n">seq</span><span class="p">[</span><span class="n">mid</span><span class="p">]</span>
</pre></div>

<p>
首先我们来看最简单的查找匹配操作，即:
</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">x</span><span class="p">):</span>
    <span class="k">return</span> <span class="n">x</span>
</pre></div>

<p>
然后我们有:
</p>
<pre>
seq = list('abcdefg')
res = binary_search(f,seq,'e')
print(res)

0 6 3
4 6 5
4 4 4
exactly
e
&gt;&gt;&gt;
</pre>

<p>
然后我们要求平方根，也就是某个x*x=target的过程，把之前定义的函数简单改一下即可:
</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">f</span><span class="p">(</span><span class="n">x</span><span class="p">):</span>
    <span class="k">return</span> <span class="n">x</span><span class="o">*</span><span class="n">x</span>
</pre></div>

<p>
然后我们利用numpy的 <code>arange</code> 函数来生成一个可能结果集。
</p>

<pre>
&gt;&gt;&gt; import numpy as np
&gt;&gt;&gt; np.arange(0,10,0.1)
array([ 0. ,  0.1,  0.2,  0.3,  0.4,  0.5,  0.6,  0.7,  0.8,  0.9,  1. ,
        1.1,  1.2,  1.3,  1.4,  1.5,  1.6,  1.7,  1.8,  1.9,  2. ,  2.1,
        2.2,  2.3,  2.4,  2.5,  2.6,  2.7,  2.8,  2.9,  3. ,  3.1,  3.2,
        3.3,  3.4,  3.5,  3.6,  3.7,  3.8,  3.9,  4. ,  4.1,  4.2,  4.3,
        4.4,  4.5,  4.6,  4.7,  4.8,  4.9,  5. ,  5.1,  5.2,  5.3,  5.4,
        5.5,  5.6,  5.7,  5.8,  5.9,  6. ,  6.1,  6.2,  6.3,  6.4,  6.5,
        6.6,  6.7,  6.8,  6.9,  7. ,  7.1,  7.2,  7.3,  7.4,  7.5,  7.6,
        7.7,  7.8,  7.9,  8. ,  8.1,  8.2,  8.3,  8.4,  8.5,  8.6,  8.7,
        8.8,  8.9,  9. ,  9.1,  9.2,  9.3,  9.4,  9.5,  9.6,  9.7,  9.8,
        9.9])
&gt;&gt;&gt;
</pre>

<p>
然后我们有:
</p>
<pre>
import numpy as np
seq = np.arange(0,10,0.000001)
res = binary_search(f,seq,2)
print(res)


nearly
1.414214
</pre>

<p>
在这里讲个题外话，提到可能结果集的时候，我就想到将多个函数参数作为(a,b,c)这种形式，可是这种多元函数问题，怎么排序，怎么比较大小，怎么确定增减性？所以只好回滚到最原始的穷举过程，这里讲的意思是计算思想很核心的一个思想就是穷举思想，然后二分查找方法是在某些条件符合的情况下的加速穷举过程。
</p>

<p>
比如说孙子算经里面的:
</p>
<blockquote>
<p>
今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？
</p>
</blockquote>

<p>
穷举的基本函数是:
</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">iter_search</span><span class="p">(</span><span class="n">f</span><span class="p">,</span><span class="n">seq</span><span class="p">,</span><span class="n">target</span><span class="p">):</span>
    <span class="k">for</span> <span class="n">item</span> <span class="ow">in</span> <span class="n">seq</span><span class="p">:</span>
        <span class="k">if</span> <span class="n">f</span><span class="p">(</span><span class="n">item</span><span class="p">)</span> <span class="o">==</span> <span class="n">target</span><span class="p">:</span>
            <span class="k">yield</span> <span class="n">item</span>
</pre></div>

<p>
很简单的一个函数，很简单的逻辑，但实际上这种先迭代某个对象，然后找到某个对象复合某个条件，则返回某个对象的过程在程序模式里面是非常常见的。
</p>

<p>
然后我们根据笛卡尔积生成可能结果集:
</p>
<pre>
&gt;&gt;&gt; from itertools import product
&gt;&gt;&gt; seq = list(product(range(35),range(35)))
&gt;&gt;&gt; seq
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), ..............
.............
</pre>

<p>
然后我们可以很直观的将问题化为两个满足条件来对可能结果集进行过滤操作:
</p>
<pre>
def f(d):
    x = d[0]
    y = d[1]
    head = x + y
    return head

def g(d):
    x = d[0]
    y = d[1]

    foot = 2*x + 4*y
    return foot
</pre>

<p>
然后我们有:
</p>
<pre>
res = list(product(range(35),range(35)))
res = iter_search(f,res,35)
res = iter_search(g,res,94)
print(list(res))

[(23, 12)]
</pre>

<p>
很简单的一些函数，但是整个过程是我很感兴趣的一种风格。
</p>
</div>
</div>


<div class="outline-3">
<h3 id="orgheadline2">binsect模块</h3>
<div class="outline-text-3" id="text-1-2">
<p>
理解这个模块最好的方法就是看源码，我们看到源码说:
</p>
<pre>
bisect = bisect_right   # backward compatibility
</pre>

<p>
所以binsect函数和bisect_right函数就是一个东西。
然后bisect_left和bisect_right其实如果列表中没有相同元素的话是没有区别的，而有相同元素的话一个选择返回插入左边的index，一个选择插入右边的index，这个了解下即可。我们来看 <code>bisect_right</code> 函数的源码:
</p>

<p>
这里python3.5版本的源码:
</p>
<div class="highlight"><pre><span></span><span class="k">def</span> <span class="nf">bisect_right</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">x</span><span class="p">,</span> <span class="n">lo</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">hi</span><span class="o">=</span><span class="bp">None</span><span class="p">):</span>
    <span class="sd">&quot;&quot;&quot;Return the index where to insert item x in list a, assuming a is sorted.</span>

<span class="sd">    The return value i is such that all e in a[:i] have e &lt;= x, and all e in</span>
<span class="sd">    a[i:] have e &gt; x.  So if x already appears in the list, a.insert(x) will</span>
<span class="sd">    insert just after the rightmost x already there.</span>

<span class="sd">    Optional args lo (default 0) and hi (default len(a)) bound the</span>
<span class="sd">    slice of a to be searched.</span>
<span class="sd">    &quot;&quot;&quot;</span>

    <span class="k">if</span> <span class="n">lo</span> <span class="o">&lt;</span> <span class="mi">0</span><span class="p">:</span>
        <span class="k">raise</span> <span class="ne">ValueError</span><span class="p">(</span><span class="s1">&#39;lo must be non-negative&#39;</span><span class="p">)</span>
    <span class="k">if</span> <span class="n">hi</span> <span class="ow">is</span> <span class="bp">None</span><span class="p">:</span>
        <span class="n">hi</span> <span class="o">=</span> <span class="nb">len</span><span class="p">(</span><span class="n">a</span><span class="p">)</span>
    <span class="k">while</span> <span class="n">lo</span> <span class="o">&lt;</span> <span class="n">hi</span><span class="p">:</span>
        <span class="n">mid</span> <span class="o">=</span> <span class="p">(</span><span class="n">lo</span><span class="o">+</span><span class="n">hi</span><span class="p">)</span><span class="o">//</span><span class="mi">2</span>
        <span class="k">if</span> <span class="n">x</span> <span class="o">&lt;</span> <span class="n">a</span><span class="p">[</span><span class="n">mid</span><span class="p">]:</span> <span class="n">hi</span> <span class="o">=</span> <span class="n">mid</span>
        <span class="k">else</span><span class="p">:</span> <span class="n">lo</span> <span class="o">=</span> <span class="n">mid</span><span class="o">+</span><span class="mi">1</span>
    <span class="k">return</span> <span class="n">lo</span>
</pre></div>

<p>
很眼熟吧，这里可能最值得关心的就是边界问题看其怎么处理的了。加入说没有重复元素x的话，那么最后收缩的情况可能是:
</p>
<pre>
low mid high
</pre>

<p>
其如果满足 x&lt;a[mid] 则:
</p>
<pre>
low high
mid
</pre>

<p>
然后会运行 low = mid + 1，程序终止，返回插入点 low + 1
</p>

<p>
如果其x&gt;=a[mid] 则:
</p>
<pre>
low high
    mid
</pre>

<p>
运行 low = mid + 1，然后返回插入点high+1。
</p>

<p>
就作为没有重复元素x的情况，上面没有问题，也可能程序直接收缩为:
</p>
<pre>
low high
mid
</pre>
<p>
等，这是没有问题。那么加入有重复元素x呢？那么程序一定会收缩并遇到a[mid] = x这样的情况，这个时候程序会小心翼翼的运行 low = mid + 1，往右移动一步。直到a[mid] = x 这样的条件不成立，然后返回low = mid +1。
</p>

<p>
然后:
</p>
<pre>
insort = insort_right   # backward compatibility
</pre>

<p>
然后insort_right的源码和bisect_right的源码基本上一模一样，除了最后加上一句:
</p>
<pre>
a.insert(lo, x)
</pre>
</div>
</div>
</div>
</div>
</body>
</html>