簡單實用演算法——二分查找法(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
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...