?

基本二分法的描述

二分搜索（英語：binary search），也稱折半搜索、對數(shù)搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

復(fù)雜度分析：最壞情況下，關(guān)鍵詞比較次數(shù)為log2(n+1)，且期望時間復(fù)雜度為O(log2n)；

作者：暴走的朝天椒，原文鏈接：https://www.jianshu.com/p/39de40ff3368

那么，有序真的是所有問題求解時使用二分的必要條件嗎？

答案是：不

只要正確構(gòu)建左右兩側(cè)的淘汰邏輯，你就可以使用二分法，那我們現(xiàn)在通過以下例子來了解二分法。

1、在一個有序數(shù)組中，找某個數(shù)是否存在

2、在一個有序數(shù)組中，找>=某個數(shù)最左側(cè)的位置

3、在一個有序數(shù)組中，找<=某個數(shù)最右側(cè)的位置

4、局部最小值問題

在一個有序數(shù)組中，找某個數(shù)是否存在

在一個有序數(shù)組中，找某個數(shù)是否存在.png??

在一個有序數(shù)組中，找大于等于某個數(shù)最左側(cè)的位置

在一個有序數(shù)組中，找大于等于某個數(shù)最左側(cè)的位置 .png??

在一個有序數(shù)組中，找小于等于某個數(shù)最右側(cè)的位置

在一個有序數(shù)組中，找小于等于某個數(shù)最右側(cè)的位置 .png

局部最小值問題

局部最小可以使用二分法完成，定義局部最小時隱含的規(guī)律即：一個不存在相同元素的數(shù)組一定存在局部最小值，因為只需要找到一個局部最小值，這樣就可以使用二分查找將數(shù)組規(guī)模逐漸減小。

1、首先判斷數(shù)組第一個值是否小于右邊的值，若小于，則局部最小值為第一個數(shù)；否則進(jìn)行下一步；

2、判斷數(shù)組的最后一個值是否小于左邊的值，若小于，則局部最小值為最后一個數(shù)；否則進(jìn)行下一步；

3、通過二分法來驗證除首位和末尾位置的數(shù)組數(shù)據(jù)的局部最小值，若某值左右兩邊的值都大于該值，那么該值就屬于局部最小值；否則繼續(xù)通過二分法進(jìn)行查找。

另外，對現(xiàn)在我們的大多數(shù)小伙伴來說編程不知道如何入門，如何打好基礎(chǔ)！栽一棵樹最好的時間是十年前，其次是現(xiàn)在。對于準(zhǔn)備學(xué)習(xí)編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！

微信公眾號：C語言編程學(xué)習(xí)基地

整理分享（多年學(xué)習(xí)的源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長比自己琢磨更快哦！