掌握二分查找

二分查找分析：二分查找是在已排序完毕的基础上进行的，用两个下标变量记录下标的移动情况，反映出查找范围的缩小，再用一个下标变量记录数组一动态元素值，将其与查找值比对是否相等。

假设查找元素33，下标变量S M E记录下标,循环查找条件为S<E,若有array[M]==33,则查找成功，返回array[M]，结束查找；否则当S大于E，返回一个统一值如-1，结束查找。

---

数组元素：11   22   33   44   55   66   77   88   99

数组下标：0     1     2     3     4     5     6     7      8

方法过程：                                                 

                  S                          M                          E       记录下标初始值，其中M=（S+E）/2

---

     下标  0    8        55

第一次循环：S<E,   array[M]>33,往左边查找，

                                        

                             下标      3   4

                                          E=M-1

             下标     1       0   3

                         M=（S+E）/2     结束第一次。

---

            下标   0  3    22

第二次循环：S<E,array[M]<33,往右边查找，

                               

                       下标  2   1

                                S=M+1

                       下标  2      2   3

                                M=（S+E）/2  结束第二次

---

           下标   2   3     33

第三次循环：S<E,array[M]==33,返回 33，全过程结束

（若是查找32，此时array[M]>32,往左边查找，

下标  1   2

          E=M-1

 下标  1       2   1

           M=（S+E）/2

第四次循环：

下标  2   1

          S>E，不满足循环条件，退出，宣告查找失败，返回一个统一值 如 -1）

---

我的代码实现：

public class BinSearch {

public static int binSearch(int[] array,int val) {

int startIndex=0,endIndex=array.length-1;//定义变量存放首尾元素下标以及中间元素下标

int midIndex=(startIndex+endIndex)/2;

while(startIndex<=endIndex) {

if(array[midIndex]==val) {

return array[midIndex];

}else if(array[midIndex]>val) {

endIndex=midIndex-1;

midIndex=(startIndex+endIndex)/2;

}else if(array[midIndex]<val) {

startIndex=midIndex+1;

midIndex=(startIndex+endIndex)/2;

}

}

return -1;

}

public static void main(String[] args) {

int[] array= {11,22,33,44,55,66,77,88,99};// TODO Auto-generated method stub

System.out.print("在下面数组中查询：\n");

for(int i=0;i<array.length;i++)

System.out.print(array[i]+" ");

System.out.println();

System.out.println("查询99结果：");

if(binSearch(array,99)==99)

System.out.println("找到 99.");

else

System.out.println("没有找到99.");

System.out.println("查询23结果：");

if(binSearch(array,23)==-1)

System.out.println("未找到。");

}

}

运行结果：

在下面数组中查询：

11 22 33 44 55 66 77 88 99

查询99结果：

找到 99.

查询23结果：

未找到。