三、Java版二分法

一、核心思想

选定这批数据中居中间位置的一个数与所查数比较，看是否为所找的数，若不是，则利用数据的有效性，可以决定所找的数是在选定数的左侧还是右侧，从而很快可以将查找范围缩小一半。以同样的方法在选定区域中进行查找，每次都会将查找范围缩小一半，从而较快的找到目的数。
有个限制条件就是：必须是有序数组！

二、源码

package com.ctw;

/**
 * @author TongWei.Chen 2018-09-25 16:20:15
 * @Description:
 * @Project sjjg-sf
 */
public class BinaryFind {

    /**
     * 二分查找
     *
     * @param arr：数组
     * @param value：所需要找的值
     * @return： 目的值所在数组的下标
     */
    public static int binaryFind(long[] arr, long value) {
        // 开始值
        int start = 0;
        // 末尾值
        int end = arr.length - 1;
        while (start <= end) {
            // 中间值，二分法嘛，先取个中再说,每次进行二分的时候都需要重新计算中间值，所以放到循环里面。
            int middle = (start + end) / 2;
            // 1.如果碰巧了，目标值直接就是中间值
            if (value == arr[middle]) {
                return middle;
            } else if(value < arr[middle]) {
                // 2.若目标值比中间值小，那肯定是在中间值左侧，则继续从0到中间值这区间进行二分查找。
                end = middle - 1;
            } else {
                // 3.若目标值比中间值大，那肯定是在中间值右侧，则继续从中间值到末尾值这区间进行二分查找。
                start = middle + 1;
            }
        }
        // 若所找的数不在数组里，则返回-1；
        return -1;
    }

    public static void main(String[] args) {
        MyArray myArray = new MyArray();
        myArray.add(1L);
        myArray.add(2L);
        myArray.add(3L);
        myArray.add(4L);
        myArray.add(5L);
        myArray.add(6L);
        myArray.add(12L);
        myArray.add(20L);
        myArray.add(30L);
        myArray.add(33L);
        int index = binaryFind(myArray.getArr(), 331L);
        System.out.println(index);
    }

}

三、广告

• 码云地址

  https://gitee.com/geekerdream/google-guava/

• QQ群【Java初学者学习交流群】：458430385

• 微信公众号【Java码农社区】

  img

• 今日头条号：编程界的小学生