• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            二分查找,是一種針對(duì)有序序列的查找方式,每次迭代會(huì)縮小一半的查找范圍,一次查找的時(shí)間復(fù)雜度為O(logN)。
            簡(jiǎn)單說一下二分查找過程:在有序序列seq[]中找一個(gè)數(shù)n,假設(shè)這個(gè)序列的起始下標(biāo)分別為a,b,mid=(a+b)/2,那么n要么就是seq[mid](n=seq[mid]),要么在mid左邊(n<seq[mid]),要么在mid右邊(n>seq[mid]),要么這個(gè)數(shù)根本不在seq[]中。

            下面這道題是二分查找的典型應(yīng)用:
            zoj1101
            題意描述:在給定整數(shù)序列(<=1000)中找出四個(gè)不同的數(shù),使得三個(gè)數(shù)的和等于另外一個(gè)數(shù)。
            直接用四層循環(huán)鐵定超時(shí),這里采用了一種拿空間換時(shí)間的方式。
            假設(shè)有a+b+d=c,這等價(jià)于a+b=c-d,我們可以把所有的a+b存起來(<=10^6個(gè)),把所有的c-d也存起來(<=10^6個(gè)),當(dāng)拿到每一個(gè)a+b時(shí)我們只需要在所有c-d的序列中查找就行了。先把c-d序列排序,排序時(shí)間復(fù)雜度O(NlogN),查找過程可以用二分,這樣就不會(huì)超時(shí)啦。
            以下是本題代碼:
            posted on 2012-08-01 21:39 小鼠標(biāo) 閱讀(1069) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 數(shù)據(jù)結(jié)構(gòu)
            <2012年8月>
            2930311234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            隨筆分類(111)

            隨筆檔案(127)

            friends

            最新評(píng)論

            • 1.?re: 線段樹
            • 是這個(gè)樣子的,所以在OJ有時(shí)候“卡住”了也不要太灰心,沒準(zhǔn)真的不是自己的原因呢。
              加油,祝你好運(yùn)啦!
            • --小鼠標(biāo)
            • 2.?re: 線段樹
            • 對(duì)于編程競(jìng)賽來說,Java所需時(shí)間一般為C/C++的兩倍。合理的競(jìng)賽給Java的時(shí)間限制是給C/C++的兩倍。
            • --傷心的筆
            • 3.?re: poj1273--網(wǎng)絡(luò)流
            • 過來看看你。
            • --achiberx
            • 4.?re: (轉(zhuǎn))ubuntu11.10無法啟動(dòng)無線網(wǎng)絡(luò)的解決方法
            • 膜拜大神。。查了一個(gè)下午資料終于在這里解決了問題。。神牛說的區(qū)域賽難道是ACM區(qū)域賽。。?
            • --Hang
            • 5.?re: 快速排序、線性時(shí)間選擇
            • 博主,謝謝你的文章。你的方法可以很好的處理分區(qū)基準(zhǔn)在數(shù)組中重復(fù)的情況,書上的方法遇到這種輸入會(huì)堆棧溢出。書上給出了解釋但給的方法貌似不簡(jiǎn)潔。
            • --lsxqw2004

            閱讀排行榜

            a级成人毛片久久| 亚洲中文字幕无码久久综合网| 久久天堂AV综合合色蜜桃网| 亚洲国产精品久久久天堂| 国产成人久久精品区一区二区| 香蕉久久一区二区不卡无毒影院| 狠狠人妻久久久久久综合| 久久婷婷色香五月综合激情| 久久99国内精品自在现线| 国产精品久久久久久久午夜片| 亚洲精品NV久久久久久久久久| 亚洲AV成人无码久久精品老人| 99精品伊人久久久大香线蕉| 亚洲综合伊人久久大杳蕉| 成人a毛片久久免费播放| 久久人人爽人人爽人人爽| 亚洲国产精久久久久久久| 亚洲欧美成人久久综合中文网 | 国产精品综合久久第一页| 18禁黄久久久AAA片| 精品久久香蕉国产线看观看亚洲| 中文字幕久久亚洲一区| 麻豆精品久久精品色综合| 亚洲va久久久噜噜噜久久男同| 久久久久久极精品久久久| 青青国产成人久久91网| 久久国产高潮流白浆免费观看| 波多野结衣久久一区二区| 久久五月精品中文字幕| 久久久精品免费国产四虎| 久久一日本道色综合久久| 久久强奷乱码老熟女网站| 综合久久精品色| 亚洲国产成人乱码精品女人久久久不卡 | 久久久久九九精品影院| 99久久亚洲综合精品网站| 久久96国产精品久久久| 好久久免费视频高清| 国产精品99久久久久久人| 久久成人国产精品| 日本一区精品久久久久影院|