二分法查找原理

1、什麼是二分法查找？

簡單粗暴一點理解二分法

（1）將數據有序排列：先將一個數據集進行有序排列（可根據某種數值的大小降序或升序<當然排序的規則可根據業務規則自定義>，前提是需要查找的數據具備該規則同樣的屬性）；

（2）數據分半：就是將排序好的數據集切分成大致相等的兩份數據；

（3）查找數據：把排序好的數據拆分為個數大致相等的兩半,因為有排序，查找的時候先和其中一半數據種的最大或者最小的數進行比較來斷定要查找的數據是否會包含被分割後的一半數據種，然後在滿足判定條件的數據集中一次獲取數據進行比對直到找到數據或者比較完所有數據返回沒有該數據，

（4）文字太蒼白：用例子進行表述一下便於我們快速理解;

題目是從[5,7,2,8,4,9,1,3,6] 快速查找到X在數據種的位置：

我們先要把 [2,-3,0,5,-1,,6] 進行排序[-3,-2,0,2,5,6] 然後進行拆分data1 [-3,-2,0] data2[2,5,8,6]

然後用查找X,是在數據中的位置，假如先從data1檢索則如下：

如果x>data1[last]

則表示X不在data1 中（因為我們已經進行了排序的），則比較對象換成data2，那麼我們把data2看成一個新的數據集繼續進行拆分，把data2拆分成data2_1 和data2_2繼續按照之前的規則進行比較，按照此規律直到找到X相同的值或者比較完data2所有的數據則返回；

如果x<data1[last]

則表示X絕對不會存在data2中（因為我們已經進行了排序的），可能存在data1中，那麼又我們把data1看成一個新的數據集繼續進行拆分，把拆data1分成data1_1 和data1_2，按照此規律直到找到X相同的值或者比較完data2所有的數據則返回；

如果x=data1[last]

那麼返回data[last]的位置;

最後一張圖來說明

2、特點

查找的時候可以減少比對數據的數量，加快查找速度，但只適用於排序數據，對數據排序本身又會消耗時間性能；

推薦閱讀：