歡迎加入QQ討論群258996829
蘋果6袋
麥子學(xué)院
Php二分法詳解
發(fā)布時間：2016-12-21 15:38 回復(fù):0 查看:2345 最后回復(fù)：2016-12-21 15:38
在php開發(fā)中，二分法應(yīng)該算是算法里最基本的一種方法了，常用于在一個有序數(shù)組中查找某個值第一次出現(xiàn)的位置、最后出現(xiàn)的位置、或者是一段區(qū)間。
有序數(shù)組中如果用暴力的貪心算法，即遍歷，時間復(fù)雜度是O(n)。
用二分法后，由于每次可以去掉一半無用的區(qū)間，會將時間復(fù)雜度減少到O(logn)。
二分法的基本做法是：
1、確定要查找的區(qū)間。
2、確定要二分時的參照點。
2、區(qū)間內(nèi)選取二分點。
3、根據(jù)二分點的值，綜合左右區(qū)間情況以及求解的目的，舍去一半無用的區(qū)間。
4、在有用的區(qū)間繼續(xù)進行二分搜索。
下面是幾道比較經(jīng)典的題目：
1、給定一個升序數(shù)組以及一個目標整數(shù)target，返回target首次出現(xiàn)的下標位置，如果不存在返回-1。
此題目已給定升序數(shù)組，所以待求區(qū)間確定，第一步就可省略了。
2、同樣是上面的題目，條件變換一下，即給定的數(shù)組可以想想為無窮大，但是你可以通過get_value($key)來獲取某個下標下的值，求target第一次出現(xiàn)的位置。
此時相當于給定的區(qū)間不確定了，所以你先要鎖定一個求解區(qū)間，增加代碼如下：
3、假設(shè)一個旋轉(zhuǎn)排序的數(shù)組其起始位置是未知的（比如0 1 2 4 5 6 7可能變成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
如上圖旋轉(zhuǎn)排序數(shù)組有以下兩種情況，兩種情況下最小元素都是小于數(shù)組中最后一個元素的，所以可以把數(shù)組最后一個元素的值當做參考點。
來源：公眾賬號
有序數(shù)組中如果用暴力的貪心算法，即遍歷，時間復(fù)雜度是O(n)。
用二分法后，由于每次可以去掉一半無用的區(qū)間，會將時間復(fù)雜度減少到O(logn)。
二分法的基本做法是：
1、確定要查找的區(qū)間。
2、確定要二分時的參照點。
2、區(qū)間內(nèi)選取二分點。
3、根據(jù)二分點的值，綜合左右區(qū)間情況以及求解的目的，舍去一半無用的區(qū)間。
4、在有用的區(qū)間繼續(xù)進行二分搜索。
下面是幾道比較經(jīng)典的題目：
1、給定一個升序數(shù)組以及一個目標整數(shù)target，返回target首次出現(xiàn)的下標位置，如果不存在返回-1。
此題目已給定升序數(shù)組，所以待求區(qū)間確定，第一步就可省略了。
2、同樣是上面的題目，條件變換一下，即給定的數(shù)組可以想想為無窮大，但是你可以通過get_value($key)來獲取某個下標下的值，求target第一次出現(xiàn)的位置。
此時相當于給定的區(qū)間不確定了，所以你先要鎖定一個求解區(qū)間，增加代碼如下：
3、假設(shè)一個旋轉(zhuǎn)排序的數(shù)組其起始位置是未知的（比如0 1 2 4 5 6 7可能變成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
如上圖旋轉(zhuǎn)排序數(shù)組有以下兩種情況，兩種情況下最小元素都是小于數(shù)組中最后一個元素的，所以可以把數(shù)組最后一個元素的值當做參考點。
來源：公眾賬號
您還未登錄，請先登錄
熱門帖子
- iDev 全平臺開發(fā)者大會門票免費送！限量10張！
- 蘋果Mac Pro垃圾桶 最低配的ME253CH
- 本人想買個蘋果電腦搞開發(fā)，哪位大俠指點下
- 求助：failable initializer 'init(name:)' cannot override a non-failable initializer
- 為慶祝Swift發(fā)布1個月，雨燕社區(qū)正式上線。
- 在UITextFeild里輸入數(shù)據(jù)，這個數(shù)據(jù)怎么做加減乘除？
- Swift 高仿喜馬拉雅FM
- 要成為自由職業(yè)者？先要學(xué)會蘋果的Swift哦
- 用swift實現(xiàn)的調(diào)用系統(tǒng)相機，相冊的DEMO
- 關(guān)于嵌入式引用\()