淺談二分策略的應(yīng)用-wenkub
2023-02-11 12:56:09 本頁面
【正文】 ：二分查找 —— 應(yīng)用于一般有序序列 ?類型二：二分枚舉 —— 應(yīng)用于退化了的有序序列 ?類型三：二分搜索 —— 應(yīng)用于無序序列 5/19/2023 3 WinterCamp 2023 類型一：二分查找 —— 應(yīng)用于一般有序序列 ?申明： “ 有序序列 ” ，僅包含兩層意思： ? 第一，它是一個 序列 ，一維的 ? 第二，該序列是 有序 的，即序列中的任意兩個元 素都是可以比較的，也就是擁有我們平時 所說的 全序關(guān)系 5/19/2023 4 WinterCamp 2023 類型一：二分查找 —— 應(yīng)用于一般有序序列 ?二分查找的一般實現(xiàn)過程： （ 1）確定查找范圍 （ 2）選擇基準元素 （ 3）關(guān)鍵字比較，確定更精確的范圍 （ 4）判斷結(jié)果，如不夠精確，轉(zhuǎn)至（ 2） 5/19/2023 5 WinterCamp 2023 例一：順序統(tǒng)計問題 ? [問題描述 ] 給定一個由 n個不同的數(shù)組成的集合 S，求其中第 i小的元素。即 N頭奶牛分成 N/2組，每組兩頭奶牛比賽，決出N/2位勝者；所有勝者繼而分成 N/4組比賽 …… 直至剩下一頭牛是冠軍。 Answer— 現(xiàn)在觀眾們想知道，哪頭奶牛是所有可能成為冠軍的牛中排名最靠后的。 ?解決方法： 枚舉！ 3?1 4?2 7?5 8?6 4?3 8?7 4?8 圖 BTP1 6?7 5?3 4?8 2?1 6?5 4?2 6?4 圖 BTP2 5/19/2023 12 WinterCamp 2023 性質(zhì)：隱含的有序性 ? 如果 排名為 X的選手最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 ?如果利用靜態(tài)排序二叉樹，整個問題可以在O(Nlog2N)時間完成。切記！? 退一步海闊天空 ?。 ?我們先任意詢問兩個點 ?不妨設(shè)詢問結(jié)果是 1到 2有邊，于是，我們就得到
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1