二分法查找

二分法查找 ：

目的 ：

查找一个数组中是否含义某个元素 ： 有返回数组中的位置 ，没有返回 -1

算法：

二分法查找适用于数据量较大时，但是数据需要先排好顺序。
算法核心思想：
二分法适用于已经排好序的数组，定义两个数组位置变量，一个low（下标为0）,一个high（数组最后一位下标）, 则mid=(low+high)/2

取一个数组中间位置元素的值 ，与查找的值进行大小比较 ：

如果 value==arr[mid],中间值正好等于要查找的值，则返回下标，return mid;
如果 value<arr[mid],要找的值小于中间的值，则再往数组的小端找（中间位置左边，数组最后一位 =>），high=mid-1;
如果 value>arr[mid],要找的值大于中间的值，则再往数组的大端找（中间位置右边，数组首位 =>），low=mid+1;

二分法查找缺点：

1、数组必须是有序的数组。　（无顺序 ，先排序 -- 需要考虑排序的效率问题）

二分法查找的优点：

1、查找次数少，效率高。

上代码 ：

package com.big.company;

import java.util.Arrays;

public class binarySearch {

    public static void main(String[] args) {

        int[] arr = {1, 3, 7, 88, 30, 20, 50, 10, 80, 9, 7, 12, 100, 40, 8};
        Arrays.sort(arr); // 先排序
        System.out.println(Arrays.toString(arr));
        System.out.println("返回位置下标 ：" + myBinarySearch(arr, 8));
    }

    public static int myBinarySearch(int[] arr, int value) {
        int low = 0; // 数组起点
        int high = arr.length - 1; // 数组终点下标

        // 不断循环 ，直到不满足条件
        while (low <= high) {
            // 数组中间点下标
            int mid = (low + high) / 2; 
            // 也许中间位置对应的值就是我们要找到值，优先判断一下
            if (value == arr[mid]) { 
                return mid;
            }
            // 要查找的值，在数组中心点的右边，数组起点更新为中心点的右边一位
            if (value > arr[mid]) {
                low = mid + 1;
            }
            // 要查找的值，在数组中心点的左边 ，数组终点下标更新为中心点左边一位
            if (value < arr[mid]) {
                high = mid - 1;
            }
        }
        return -1;//没有找到返回-1
    }
}

Arrays 类中已经为我们实现 ：
Arrays 类中还有许多帮助方法（such as sorting and searching ），大家可以查看一下源码

    // Like public version, but without range checks.
    private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

相关参考： https://blog.csdn.net/lee514/article/details/82977044

---

如果您能从文字中学到东西，请帮忙点赞 👍 ，😘😘😘 赠人玫瑰，手留余香

致成长之路

---