算法：二分查找法

发表于   |   分类于 ，   |   阅读次数

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

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

正文

概述

二分查找法，也叫折半查找法，提供一个升序的需要查找数组，再一分为二分别使用左右指针循环匹配，不断测算需要查找的区间，不断进行将数组折半。二分查找法的效率非常高，但是很少人能写出稳定的二分查找法（本来想写很少人能写出没有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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int binarySearch(int key,int[] array) {
        int start,end,mid = 0;
        start=0;
        end=array.length-1;
        while (start<=end) {
            mid=(start+end)/2;//测算中间位置
            if(array[mid]==key){
                return mid;
            }else if(array[mid]>key){//测算该值在数组的左边还是右边
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return -1;
}