簡單實用演算法——二分查找法(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
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...