参考链接(如有侵权立即删除)#

二分查找有几种写法？它们的区别是什么？——知乎
 二分查找算法（左闭右开区间）
二分查找法——百度百科

正文#

概述#

二分查找法，也叫折半查找法，提供一个升序的需要查找数组，再一分为二分别使用左右指针循环匹配，不断测算需要查找的区间，不断进行将数组折半。二分查找法的效率非常高，但是很少人能写出稳定的二分查找法（本来想写很少人能写出没有bug的二分查找法，但是想想欠妥，哪有没有bug的程序）

实现原理#

注：现在是需要查找的数组中只有非负整数

先有一个升序了的数组#

首先需要一个已经升序排序过的数组，假设现在有数组，int[] score={67,69,75,88,99,103},假设我们需要查找int key=67吧，

0	1	2	3	4	5
67	69	75	88	99	103

测算中间位置，开始一分为二#

测算中间值，我们通过开始下标和结束下标来算中间位置，int mid=(start+end)/2;，由于申明的是int,5/2取得double值只会取整数部分，由此可知，中间值为75，int left=0,right=score.length-1，left和right，是用来控制范围，每次我们都会缩小范围查找。

0	1	2	3	4	5
67	69	==75==	88	99	103
↑L					↑R

缩小左右区间#

我们将需要查找的值67 与mid，对比，发现67比mid大，那么由于数组已经是升序的，我们大概推算出，67应该是在0到2的下标之间，将范围缩小，right=mid-1，将范围缩小到0-1。

0	1	2	3	4	5
67	69	==75==	88	99	103
↑L	↑R

循环折半查找#

现在我们要重新测试中间值，以继续进行折半查找,int mid=(start+end)/2;，由此可知中间值67，判断if(mid==key)，查找结束，找到下标为0。

0	1	2	3	4	5
==67==	69	75	88	99	103
↑L	↑R

源码#

1
public static int binarySearch(int key,int[] array) {
2
        int start,end,mid = 0;
3
        start=0;
4
        end=array.length-1;
5
        while (start<=end) {
6
            mid=(start+end)/2;//测算中间位置
7
            if(array[mid]==key){
8
                return mid;
9
            }else if(array[mid]>key){//测算该值在数组的左边还是右边
10
                end=mid-1;
11
            }else{
12
                start=mid+1;
13
            }
14
        }
15
        return -1;
16
}