二分查找

二分查找也叫作折半查找。二分查找有兩個要求，壹個是數列有序，另壹個是數列使用順序存儲結構。他的思想很簡單，但是在書寫過程中如果邊界條件無法正確的確定，很容易 陷入到循環中無法跳出 。

二段性是集合中的元素有存在 分界線 ，給定條件可以將集合中元素分為兩部分，壹部分滿足條件，壹部分不滿足條件。

對於壹個給定的數組 進行二分查找時，需考慮以下步驟

面對 查找小於 的最後壹個數 時，如果令左邊界的值為 ，那麽左邊界的初始條件已經不滿足問題要求了，因此采用0作為壹個通用的二分求解方法的左邊界並不是壹個合理的方案。

同理，面對 查找大於 的第壹個數 ，也不可以令右邊界的值為1。

采用其他的公式，比如 ，也是可以的，但是為了防止 與 相加 導致的數值溢出 使用上面的公式。

為了避免寫出死循環， 必須保證每次進入 之後，可行區間都在變小，且最終推出循環 。在此先引出程序終止的條件為 ，當面對 ，此時以滿足終止條件所以無論 和 取多少，都會退出循環；當面對 ，中點為 ，此時循環體內的收縮公式會將 賦值給 或者 ，再此達到終止條件，退出循環；當面對 ，按照 裏的分析，其最終會進入到 或者 的條件。

因為的目標時遍歷整個數組，因此 終止條件要確保所有的元素都可以被包含在內 。同上面的收縮區間的公式相配合可以構成壹個二分查找。

和 的指向哪個數值，最終還是取決於judge條件。對於我們要查找小於零第壹個數，其judge條件為 ， ， 。

參考文獻：