作者：liubird
來源：http://blog.chinaunix.net/uid-1844931-id-3337784.html
前幾天，在論壇上看到有統計說有90%的程式設計師不能夠寫對簡單的二分法。二分法不是很簡單的嗎？ 這難道不是聳人聽聞？
其實，二分法真的不那麼簡單，尤其是二分法的各個變種。 最最簡單的二分法，就是從一個排好序的數組之查找一個key值。 如下面的程序。
這個程序，相信只要是一個合格的程式設計師應該都會寫。 稍微注意一點， 每次移動left和right指針的時候，需要在mid的基礎上+1或者-1， 防止出現死循環， 程序也就能夠正確的運行。
但如果條件稍微變化一下， 你還會寫嗎？如，數組之中的數據可能可以重複，要求返回匹配的數據的最小（或最大）的下標；更近一步， 需要找出數組中第一個大於key的元素（也就是最小的大於key的元素的）下標，等等。 這些，雖然只有一點點的變化，實現的時候確實要更加的細心。 下面列出了這些二分檢索變種的實現。
1、找出第一個與key相等的元素
2、找出最後一個與key相等的元素
3、查找第一個等於或者大於Key的元素
4、查找第一個大於key的元素
5、查找最後一個等於或者小於key的元素
6、查找最後一個小於key的元素
接下來，大家可以對這四種變種算法進行相應的測試。
很多的時候，應用二分檢索的地方都不是直接的查找和key相等的元素，而是使用上面提到的二分檢索的各個變種，熟練掌握了這些變種，當你再次使用二分檢索的檢索的時候就會感覺的更加的得心應手了。
（完）
這裡，我留給大家一個問題，這種 mid = (left + right) / 2 的寫法有什麼不足，該怎麼改進呢？如果你用過jdk的二分查找，肯定就知道答案了（提示：Collections.binarySearch()）。這裡不提倡大家為了讀源碼而讀源碼，一般來說，帶有目的性的讀源碼才會有較大的幫助。