一、整數(shù)二分

整數(shù)二分說明

• 整數(shù)二分即為在整數(shù)集合上的二分，常見的用法有：在單調(diào)序列中查找「某個數(shù)是否出現(xiàn)過」、「某個數(shù)最早出現(xiàn)的位置」以及「>= 某個數(shù)中最小的數(shù)」等。
• 解決這類問題的思想非常統(tǒng)一，即對坐標區(qū)間不斷進行折半，以此在 O(log(n)) 的時間復(fù)雜度內(nèi)確定答案，但其「實現(xiàn)方法」卻非常多樣，由此導(dǎo)致很多同學(xué)在此類問題上出錯。
• 因此接下來將通過一個例題來介紹「記錄 ans」的二分實現(xiàn)方法，該方法較易理解且不易出錯。

整數(shù)二分示例

在排序數(shù)組中查找元素的第一個和最后一個位置。

① 題目說明

• 題目描述：給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標值 target。找出給定目標值在數(shù)組中的開始位置和結(jié)束位置，如果數(shù)組中不存在目標值 target，返回 [-1, -1]。設(shè)計并實現(xiàn)時間復(fù)雜度為 O(log(n)) 的算法解決此問題。
• 示例一：

輸入：nums = [5,7,7

總結(jié)

以上是生活随笔為你收集整理的【数据结构与算法】之面试必考的“二分算法”系统梳理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。