最近重新開(kāi)始學(xué)習(xí)算法烙肺，因?yàn)橛X(jué)得這個(gè)一個(gè)本質(zhì)的思想性的東西钦勘，無(wú)論何時(shí)，都可以從此收益棋傍，于是打算記錄一下自己學(xué)習(xí)算法的一些體會(huì)救拉。
二分法應(yīng)該算是算法里最基本的一種方法了，常用于在一個(gè)有序數(shù)組中查找某個(gè)值第一次出現(xiàn)的位置瘫拣、最后出現(xiàn)的位置亿絮、或者是一段區(qū)間。
有序數(shù)組中如果用暴力的貪心算法麸拄，即遍歷派昧，時(shí)間復(fù)雜度是O(n)。
用二分法后拢切，由于每次可以去掉一半無(wú)用的區(qū)間蒂萎，會(huì)將時(shí)間復(fù)雜度減少到O(logn)。
二分法的基本做法是：
1淮椰、確定要查找的區(qū)間五慈。
2纳寂、確定要二分時(shí)的參照點(diǎn)。
2泻拦、區(qū)間內(nèi)選取二分點(diǎn)毙芜。
3、根據(jù)二分點(diǎn)的值争拐，綜合左右區(qū)間情況以及求解的目的腋粥，舍去一半無(wú)用的區(qū)間。
4架曹、在有用的區(qū)間繼續(xù)進(jìn)行二分搜索灯抛。
下面是幾道比較經(jīng)典的題目：
1、給定一個(gè)升序數(shù)組以及一個(gè)目標(biāo)整數(shù)target音瓷，返回target首次出現(xiàn)的下標(biāo)位置，如果不存在返回-1夹抗。
此題目已給定升序數(shù)組绳慎，所以待求區(qū)間確定，第一步就可省略了漠烧。
2杏愤、同樣是上面的題目，條件變換一下已脓，即給定的數(shù)組可以想想為無(wú)窮大珊楼，但是你可以通過(guò)get_value($key)來(lái)獲取某個(gè)下標(biāo)下的值，求target第一次出現(xiàn)的位置度液。
此時(shí)相當(dāng)于給定的區(qū)間不確定了厕宗，所以你先要鎖定一個(gè)求解區(qū)間，增加代碼如下：
3堕担、假設(shè)一個(gè)旋轉(zhuǎn)排序的數(shù)組其起始位置是未知的（比如0 1 2 4 5 6 7可能變成是4 5 6 7 0 1 2）已慢。你需要找到其中最小的元素。你可以假設(shè)數(shù)組中不存在重復(fù)的元素霹购。
如上圖旋轉(zhuǎn)排序數(shù)組有以下兩種情況佑惠，兩種情況下最小元素都是小于數(shù)組中最后一個(gè)元素的，所以可以把數(shù)組最后一個(gè)元素的值當(dāng)做參考點(diǎn)齐疙。
