顺序查找、二分查找

一、基本查找（顺序查找）：从前往后，挨个查找

二、二分查找（折半查找）

1、前提条件：数组中的数据必须是有序的。

2、核心思想：每次排除一半的数据，查询数据的性能明显提高极多。

举例：从一组数据中，找出79。

第一步：从小到大排序。

第二步：

此时目标值79小于81，因此要将right移到mid左侧。

第三步：

此时目标值79大于23，因此要将left移到mid右侧。

第四步：

此时目标值79等于79，找到。

3、特殊情况：

此时数组中没有我们要找的数字150，目标值150大于147。

因此需要将left移到mid右侧。

此时left在right右侧，已经发生了错位，找不到目标值150，因此就结束二分查找。

所以得出结论：二分查找正常的折半条件应该是开始位置left <= 结束位置right。

4、代码演示

public class Test3 {
    public static void main(String[] args) {
        //1、准备好一个数组
        int[] arr = {81, 7, 79, 23, 103, 127, 147, 131};

        System.out.println(binarySearch(arr, 81));
    }

    public static int binarySearch(int[] arr, int data){
        //1、先对数组进行排序（从小到大）
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        //2、定义两个变量，开始二分查找
        int left = 0;
        int right = arr.length-1;
        int mid;
        while(left<=right){
            mid = (left + right)/2;
            if(arr[mid]==data){
                return data;
            }
            if(arr[mid]>data){
                right = mid-1;
                continue;
            }
            if(arr[mid]<data){
                left = mid+1;
                continue;
            }
        }
        //如果没找到，就返回-1
        return -1;
    }
}

当然，如果我们不想要找到的目标值，也可以将mid返回。

其实，Java的Arrays工具类已经写好了二分查找，即Arrays.binarySearch(要查找的数组，目标值)，返回值为目标值的下标。