二分查找板子

来源:https://www.cnblogs.com/D-booker/archive/2022/05/07/16241843.html
-Advertisement-
Play Games

二分查找實際上就是採用了分治法的思想 以下模板都以升序數組為準 模板一: 標準的二分查找 場景:數組元素有序且不重覆 有的話返回索引,沒有返回-1 int binarySearch(vector<int>& arr, int target) { int left = 0, right = nums. ...


二分查找實際上就是採用了分治法的思想

以下模板都以升序數組為準

模板一: 標準的二分查找

場景:數組元素有序且不重覆

有的話返回索引,沒有返回-1

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {//<=指可以取到右區間,是[left,right]
        int mid = left + ((right - left) >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] > target) right = mid - 1;//證明target可能在mid左側
        else left = mid + 1;//證明nums[mid] < target, target可能在mid右側
    }
    
    return -1;
}

模板二:二分查找找邊界

二分查找左/有邊界是二分查找的變式,一般有如下場景:

1)第一種情況

  • 數組總體有序,包含重覆元素
  • 數組部分有序,且不包含重覆元素

2)第二種情況

  • 數組部分有序,且包含重覆元素

二分查找找左邊界

1)針對第一種情況:

int binarySearch(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {//這是左閉右開[,),不包含最後一個數,left = right 的時候會跳出
        int mid = left + ((right - left) >> 1);
        if (nums[mid] < targrt) left = mid + 1;
        else right = mid;//nums[mid] >= target, 都需要往左邊收縮邊界(主要)
    }
    //因為裡面是沒有判斷left = right 這個索引的位置,需要打個補丁
    return nums[left] == target ? left : -1;
}

2)針對第二種情況(模板有誤)


二分查找找右邊界

1)針對第一種情況

int binarySearch(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {
        mid = left + ((right - left) >> 1) + 1;//需要註意,這裡多加了個1,這樣無論是奇偶數,中間位置都偏右,這樣避免了死迴圈(如果不加1,比如{2,2}就會死迴圈
        if (nums[mid] > target) right = mid - 1;//收縮右邊界
        else left = mid;//numd[mid] <= target,都需要收縮左邊界(主要)
    }
    //打個補丁,這裡寫左右都可以
    return nums[left] == target ? left : -1;
}

2)針對第二種情況


二分查找找左右邊界

分別查找左右邊界即可

1)第一種情況

vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res{-1,-1};//res[0]存左邊界,res[1]存右邊界
    
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left < right) {//先找左邊邊界
        mid = left + ((right - left) >> 1);
        if (nums[mid] < target) left  = mid + 1;
        else right = mid;
    }
    res[0] = nums[left] == target ? left : -1;
    
    if (res[0] != -1) {//存在左邊邊界查找右邊邊界
        if (left == nums.size() - 1 || nums[left + 1] != target) {//可能只有一個target,它的位置可能在末尾/其他位置
            res[1] = left;
        }
        else {//有多個target
            right = nums.size() - 1;
            
            while (left < right) {
                mid = left + ((right - left) >> 1) + 1;
                if (nums[mid] > target) right = mid - 1;
                else left = mid;
            }
            res[1] = nums[left] == target ? left : -1;
        }
    }
    
    return res;
}

模板三:二分查找找極值點

二分查找的一種變式:找極值,即是v或者^的最值點;

我們查找的時候不再是和target進行比較,而是和相鄰元素比較,以達到某種單調區間檢測的效果

下麵以查找^的極值點寫一個模板:

int binarySearch(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    int mid;
    
    while (left <= right) {
       mid = left + ((right - left) >> 1);
       
        if (nums[mid] > nums[mid] + 1 && nums[mid] > nums[mid - 1]) return mid;
        else if (nums[mid] > nums[mid + 1]) right = mid - 1;//極值點在左邊
        else left = mid + 1;//極值點在右邊
    }
    
    return -1;
}

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

-Advertisement-
Play Games
更多相關文章
  • Spring Ioc源碼分析系列--Ioc源碼入口分析 本系列文章代碼基於Spring Framework 5.2.x 前言 上一篇文章Spring Ioc源碼分析系列--Ioc的基礎知識準備介紹了Ioc的基礎概念以及Spring Ioc體系的部分基礎知識。那麼這一篇就會真正通過一個例子,啟動Ioc ...
  • 前言 有時候我們些代碼是總發此疑惑? 為什麼別人採集 xx 網站的時候能成功,而我卻總是不返回給數據 出現這種原因時往往是我們沒有給夠偽裝, 被識別了出來~ 就像人,你出門肯定是要穿衣服的對不,如果你不穿! 走在外面,肯定是最顯眼的一個,不抓你抓誰 還有一種就是明明我之前運行成功了,為什麼我現在再次 ...
  • 用python的pandas庫進行數據分析,分析對象是老番茄B站數據。 pandas常用基礎數據分析代碼。 ...
  • 給開源項目尤其是Spring這種知名度高的項目貢獻代碼是比較難的,起碼胖哥是這麼認為的。有些時候我們的靈感未必契合作者的設計意圖,即使你的代碼十分優雅。 我曾經給Spring Security提交了一個我認為非常重要的一項優化,和作者溝通了幾十個來回無法說服他。人家說留了抽象介面,你覺得不對自己實現 ...
  • 作者:CadeCode 地址:https://juejin.cn/post/7043403364020781064 斷言 斷言是一個邏輯判斷,用於檢查不應該發生的情況 Assert 關鍵字在 JDK1.4 中引入,可通過 JVM 參數-enableassertions開啟 SpringBoot 中提 ...
  • Python 是一種極其多樣化和強大的編程語言!當需要解決一個問題時,它有著不同的方法。在本文中,將會展示列表解析式 (List Comprehension)。我們將討論如何使用它?什麼時候該或不該使用它? 列表解析式的優勢 •比迴圈更節省時間和空間。 •需要更少的代碼行。 •可將迭代語句轉換為公式 ...
  • Python代碼規範 代碼規範這東西也是很重要的,一定要註意 給你舉個例子: 你代碼全部寫對了,但是你的代碼規範沒弄好,找個半天,不知道錯哪了,那感覺,簡直不要太崩潰 好啦,下麵我們開始學習吧~ 一、簡明概述 1、編碼 如無特殊情況, 文件一律使用 UTF-8 編碼如無特殊情況, 文件頭部必須加入 ...
  • 一個工作了4年的小伙伴,他說他從線下培訓就開始接觸Spring,到現在已經快5年時間了。 從來沒有想過,為什麼要使用Spring 框架。 結果在面試的時候,竟然遇到一個這樣的問題。 大腦一時間短路了,來求助我,這類問題應該怎麼去回答。 下麵我們來看看普通人和高手的回答 普通人: 嗯。。。。。。。。。 ...
一周排行
    -Advertisement-
    Play Games
  • 前言 本文將以 C# 語言來實現一個簡單的布隆過濾器,為簡化說明,設計得很簡單,僅供學習使用。 感謝@時總百忙之中的指導。 布隆過濾器簡介 布隆過濾器(Bloom filter)是一種特殊的 Hash Table,能夠以較小的存儲空間較快地判斷出數據是否存在。常用於允許一定誤判率的數據過濾及防止緩存 ...
  • 目錄 一.簡介 二.效果演示 三.源碼下載 四.猜你喜歡 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 轉場 零基礎 O ...
  • 「簡單有價值的事情長期堅持做」 這是成功最簡單,但也最難學的秘訣。不經過訓練,人很難意識到時間複利的威力。 仙劍奇俠傳的「十里坡劍神」和金庸群俠傳的「十級野球拳」,就是簡單的事情持之以恆反覆做,最後就有巨大的威力 唐家三少成為網文收入第一,最重要的一步是十四年從未斷日更 這樣的案例很多,一開始可能成 ...
  • 迎面走來了你的面試官,身穿格子衫,挺著啤酒肚,髮際線嚴重後移的中年男子。 手拿泡著枸杞的保溫杯,胳膊夾著MacBook,MacBook上還貼著公司標語:“我愛加班”。 面試開始,直入正題。 面試官: 看你簡歷上面寫著精通MySQL,我先問你事務的特性是什麼? 老生常談,這個還有誰不會背的嗎? 我: ...
  • 基礎知識 python是一門腳本語言,它是解釋執行的。 python使用縮進做為語法,而且python2環境下同一個py文件中不能同時存在tab和空格縮進,否則會出錯,建議在IDE中顯示縮進符。 python在聲明變數時不寫數據類型,可以type(xx)來獲取欄位的類型,然後可以int(),list ...
  • 為什麼要多線程下載 俗話說要以終為始,那麼我們首先要明確多線程下載的目標是什麼,不外乎是為了更快的下載文件。那麼問題來了,多線程下載文件相比於單線程是不是更快? 對於這個問題可以看下圖。 橫坐標是線程數,縱坐標是使用對應線程數下載對應文件時花費的時間,藍橙綠代表下載文件的大小,每個線程下載對應文件2 ...
  • 詳細講解python爬蟲代碼,爬微博搜索結果的博文數據。 爬取欄位: 頁碼、微博id、微博bid、微博作者、發佈時間、微博內容、轉發數、評論數、點贊數。 爬蟲技術: 1、requests 發送請求 2、datetime 時間格式轉換 3、jsonpath 快速解析json數據 4、re 正則表達式提... ...
  • 背景: 一般我們可以用HashMap做本地緩存,但是HashMap功能比較弱,不支持Key過期,不支持數據範圍查找等。故在此實現了一個簡易的本地緩存,取名叫fastmap。 功能: 1.支持數據過期 2.支持等值查找 3.支持範圍查找 4.支持key排序 實現思路: 1.等值查找採用HashMap2 ...
  • 目錄 一.簡介 二.效果演示 三.源碼下載 四.猜你喜歡 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 轉場 零基礎 O ...
  • 本章是系列文章的第八章,用著色演算法進行寄存器的分配過程。 本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技 寄存器分配 寄存器分配是為程式處理的值找到存儲位置的問題 這些值可以存放到寄存器,也可以存放在記憶體中 寄存器更快,但數量有限 記憶體很多,但 ...