簡單實用演算法——二分查找法(BinarySearch)

来源:https://www.cnblogs.com/timefiles/archive/2020/07/25/BinarySearch.html
-Advertisement-
Play Games

二分查找(英語:binary search),也叫折半查找(英語:half-interval search),是一種在有序數組中查找特定元素的搜索演算法。所以,二分查找的前提是數組必須是有序的。 二分查找只適用順序存儲結構。為保持表的有序性,在順序結構里插入和刪除都必須移動大量的結點。因此,二分查找特... ...


演算法概述

二分查找(英語:binary search),也叫折半查找(英語:half-interval search),是一種在有序數組中查找特定元素的搜索演算法。所以,二分查找的前提是數組必須是有序的。
時間複雜度、空間複雜度請參照下圖(圖片來自wikipedia):

適用情況

二分查找只適用順序存儲結構。為保持表的有序性,在順序結構里插入和刪除都必須移動大量的結點。因此,二分查找特別適用於那種一經建立就很少改動、而又經常需要查找的線性表

對那些查找少而又經常需要改動的線性表,可採用鏈表作存儲結構,進行順序查找。鏈表上無法實現二分查找(更準確的說鏈表上使用二分查找得不償失)

演算法原理

二分查找的基本思想是:

  • R[low…..high]是當前的查找區間
  • 首先確定該區間的中點位置:mid = low + ((high - low) >> 1)
  • 然後將待查的target值與ary[mid]比較:若相等,則查找成功並返回此位置,否則須確定新的查找區間,繼續二分查找。
  • 若ary[mid]>target,則由表的有序性可知ary[mid….high]均大於K,因此若表中存在關鍵字等於target的結點,則該結點必定是在位置mid左邊的子表R[low…mid-1]中,故新的查找區間是左子表ary[low…...mid-1]
  • 若ary[mid]<target,則要查找的target必在mid的右子表ary[mid+1……high]中,即新的查找區間是右子表ary[mid+1……high]
  • 下一次查找是針對新的查找區間進行的。

因此,從初始的查找區間R[0..n-1]開始,每經過一次與當前查找區間的中點位置上的結點關鍵字的比較,就可確定查找是否成功,不成功則當前的查找區間就縮小一半。這一過程重覆直至找到關鍵字為target的結點,或者直至當前的查找區間為空(high<low,即查找失敗)時為止。

演算法實現(C#)

演算法基於C#編寫,有簡單和泛型兩種實現,每種實現又分遞歸版本、While迴圈版本。實際運用時,推薦使用While迴圈版本的二分查找
演算法代碼如下:

    //此演算法假定數組已排序;如果不是這樣,則結果將不正確。
    class BinarySearch
    {
        //不要使用mid = (high + low) / 2,可能會導致運算溢出
        #region 簡單
        // 遞歸版本           
        public static int Recursive(int[] ary, int target)
        {
            return Recursive(ary, 0, ary.Length-1, target);           
        }
        static int Recursive(int[] ary, int low, int high, int target)
        {
            if (high < low) return -1;    
            int mid = low + ((high - low) >> 1);
            if (ary[mid] == target) return mid;
            if (ary[mid] > target)
            {
                return Recursive(ary, low, mid-1, target);
            }
            else
            {
                return Recursive(ary, mid + 1, high, target);
            }            
        }
        //While迴圈版本
        public static int WhileLoop(int[] ary, int target)
        {
            int low = 0; 
            int high = ary.Length - 1;
            while (low <= high)
            {                                
                int mid = low + ((high - low) >> 1);
                if (ary[mid] == target) return mid;
                if (ary[mid] > target)
                {
                    high = mid - 1;
                }
                else 
                {
                    low = mid + 1;
                }
            }
            return -1;
        }
        #endregion
        
        #region 泛型
        // 遞歸版本           
        public static int RecursiveT<T>(T[] ary, T target) where T : IComparable
        {
            return RecursiveT(ary, 0, ary.Length - 1, target);
        }
        static int RecursiveT<T>(T[] ary, int low, int high, T target) where T : IComparable
        {               
            if (high < low) return -1;            
            int mid = low + ((high - low) >> 1);
            int cr = Comparer.Default.Compare(ary[mid], target);             
            if(cr==0)return mid;
            if (cr > 0)
            {
                return RecursiveT(ary, low, mid - 1, target);
            }
            else 
            {
                return RecursiveT(ary, mid + 1, high, target);
            }            
        }
        //While迴圈版本
        public static int WhileLoopT<T>(T[] ary, T target) where T : IComparable
        {
            int low = 0;
            int high = ary.Length - 1;
            while (low <= high)
            {                
                int mid = low + ((high - low) >> 1);
                int cr = Comparer.Default.Compare(ary[mid], target);                
                if (cr == 0) return mid;
                if (cr>0)
                {
                    high = mid - 1;
                }
                else 
                {
                    low = mid + 1;
                }               
            }
            return -1;
        }
        //預設情況下推薦使用While迴圈版本
        public static int DefaultT<T>(T[] ary, T target) where T : IComparable 
        {            
            return WhileLoopT(ary, target);
        }
        #endregion 
    }

測試代碼如下:

//數組必須有序
//此處用升序遞增的整數數組是為了便於檢查結果
int[] ary = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }; 
long[] aryT = new long[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };            
int target = 8;
int r = BinarySearch.Recursive(ary, target);
int w = BinarySearch.WhileLoop(ary, target);
int rT = BinarySearch.RecursiveT(ary, target);
int wT = BinarySearch.WhileLoopT(ary, target);
Console.WriteLine("r={0} w={1} rT={2} wT={3}", r, w, rT, wT);

實際應用:用二分查找法找尋邊界值

在集合中找到一個大於(小於)目標數t的數x,使得集合中的任意數要麼大於(小於)等於x,要麼小於(大於)等於t。
舉例來說:給予數組和目標數

int array = {2, 3, 5, 7, 11, 13, 17};
int target = 7;

那麼上界值應該是11,因為它“剛剛好”大於7;下界值則是5,因為它“剛剛好”小於7。

該問題不能直接使用二分查找的實現代碼解決,需要對代碼做一些修改,但解題思路還是二分查找。

實現代碼如下:

//用二分查找法找尋上界
static int BSearchUpperBound(int[] ary, int target)
{           
    int low = 0;
    int high = ary.Length - 1;            
    while (low <= high)
    {
        int mid = low + ((high - low) >> 1);
        if (high == low) 
        {
            if (ary[mid] > target) return mid;
            else return -1;            
        }
        if (ary[mid] > target)
        {
            //當前找到的數大於目標數時,它可能就是我們要找的數,所以需要保留這個索引
            high = mid ;
        }
        else
        {
            //當前找到的數小於等於目標數時繼續向上取區間
            low = mid + 1;
        }
    }
    return -1;        
}
 //用二分查找法找尋下界
static  int BSearchLowerBound(int[] ary, int target)
{
    int low = 0;
    int high = ary.Length - 1;
    while (low <= high)
    {
        //取中間索引時使用向上取整,否則low無法往上爬到下界值
        int mid = low + ((high - low + 1) >> 1);
        if (high == low)
        {
            if (ary[mid] < target) return mid;
            else return -1;
        }               
        if (ary[mid] >= target)
        {
            //當前找到的數大於等於目標數時繼續向下取區間
            high = mid-1;
        }
        else
        {
            //當前找到的數小於目標數時,它可能就是我們要找的數,所以需要保留這個索引
            low = mid;
        }
    }
    return -1;
}

測試代碼如下:

//尋找邊界值
int[] array =new int[]{ 2, 3, 5, 7, 11, 13, 17 };
int target =6;
//用二分查找法找尋上屆
int up = BSearchUpperBound(array, target);
int lo=BSearchLowerBound(array, target);

參考文章

二分搜索(Binary_Search)——簡書
binary search——百度百科
BinarySearch——.NET源碼
二分查找BinarySearch原理分析、判定樹、及其變種——CSDN
二分查找法的實現和應用彙總——CSDN


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 3.色彩空間 色彩空間¶ 下麵的圖的三個點表示的是RGB,當三個通道全是0時是黑色,全是255時是白色。 常見的色彩空間 1.色彩空間轉換的API¶ cv.cvtColor(圖片,cv.COLOR_BGR2+“色彩空間”) In [4]: import cv2 as cv def color_spa ...
  • 2.圖像方面Numpy數組相關操作 In [1]: import cv2 as cv import numpy as np #圖片顏色反轉 def access_pixels(img): print(img.shape) height=img.shape[0] width=img.shape[1] ...
  • 1.opencv基礎 In [1]: import cv2 as cv #讀出video #打開指定路徑下的視頻文件:cap =cv2.VideoCapture(path) #讀取每一幀:flag,frame = cap.read(),打開視頻並讀取每一幀圖片,將視頻轉換為4維的矩陣 def vid ...
  • 點擊此處進入下載地址 提取碼:2wg3 資料簡介: 本書採用獨創的黑箱模式,MBA案例教學機制,結合一線實戰案例,介紹Sklearn人工智慧模塊庫和常用的機器學習演算法。書中配備大量圖表說明,沒有枯燥的數學公式,普通讀者,只要懂Word、Excel,就能夠輕鬆閱讀全書,並學習使用書中的知識,分析大數據 ...
  • @ 前言 JVM的自動記憶體管理得益於不斷發展的垃圾回收器,從最初的單線程收集到現在併發收集,垃圾回收器的開發者們一直在致力於如何降低GC過程中的停頓時間(STW)以及提高吞吐量,但直到現在也不存在一款完美的垃圾回收器,只能根據不同的場景選擇最合適的。所以需要瞭解每款垃圾回收器出現的背景、原因,並掌握 ...
  • java培訓主要包含哪些方面的學習?主要先學Java基礎,包括java語法,面向bai對象特征,常見API,集合du框架,在這方面需要學習到很多東西,需要夯實語法基礎,鍛煉編程思維,其實java語法基礎不難的,但是一定要學的特別扎實,才可以為後期學習做好基礎。 世界其實一直都在變化,每天都有新鮮事物 ...
  • 現在有越來越多的新技術東西、新言語涌現,如2015年5月發佈的Rust1.0、2014年出現的Hack和Swift,今年還出現了雲表0代碼編程...... 面臨林林總總的言語,我總是能收到IT新人、小白的疑問,這麼多言語我應該先學哪一種?什麼言語值得咱們長期地學習?學完之後工作開展前景大嗎? 在此我 ...
  • 「開發流程」在不同的產品項目中,不同規模的企業中,往往也不盡相同,有瀑布、有敏捷,但最基本的開發流程理當如圖所示,也是最簡單最容易實操,公認度最高 如果實踐這套流程,說明你們在甲方爸爸面前比較硬氣的那種。往往我們都做處在另一個痛苦的流程:甲提給運維或開發,今天明天要,加班實現,甲改需求,加班修改.. ...
一周排行
    -Advertisement-
    Play Games
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...