Java基础——线性、二分查找算法

一、线性查找法：

又称为顺序查找。在一列给定的值中进行搜索，从一端开始逐一检查每个元素，直到找到所需元素的过程。

举个例子：

//先定义一个数组，然后我们获取用户输入的数字，在下面的数组中查找，如果找到就输出该数字的下标
int [] array = {10,12,15,8,19,20,18,60,53,48,29};
public static void main(String[] args) {
System.out.println("请输入要查找的数字：");
        Scanner input = new Scanner(System.in);
        int num_input = input.nextInt();
        
        int index = -1;//保存找到数字的下标，如果没有则是-1
        for(int i = 0 ; i < array.length ; i++) {
            if(num_input == array[i]) {
                index = i;
            }
        }
        if(index == -1) {
            System.out.println("没有找到输入的数字");
        }else {
            System.out.println("输入的数字在第" + (index+1) + "个");
        }
}

---

如果需要我们取出数组中的最大值，我们也可以用这种方法实现：

public static void main(String[] args) {
        int max = array[0];
        for(int i = 0 ; i < array.length ; i++) {
            if(max<array[i]) {
                max = array[i];
            }
        }
        System.out.println("数组中最大值是" + max);
｝

二、二分查找算法

又称为折半查找法。将数组中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将数组分成前后两个子数组，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子数组，否则进一步查找后一子数组，重复以上过程，知道找到或找不到为止。不过这种方法只能对有序的数组（即已经排好序的数组）。

示例代码：

//还是先定义一个数组，然后我们获取用户输入的数字，在下面的数组中查找，如果找到就输出该数字的下标
 int[] array = { 1, 3, 5, 6, 8, 16, 18, 22, 28 };
 
 public static void main(String[] args) {
        
        System.out.println("请输入要查找的数字：");
        Scanner input = new Scanner(System.in);
        int number = input.nextInt();
        int index = -1;// 保存找到数字的下标，如果没有则是-1
        int start = 0;// 起始下标
        int end = array.length - 1;// 终止下标
        int middle;// 中间下标

        while (start <= end) {
            // 找到中间下标所对应的的元素值
            middle = (start + end) / 2;
            int num_middle = array[middle];
            
            if (number == num_middle) {
                index = middle;
                break;
            }
            // 如果要查找的数值大于中间值
            if (number > num_middle) {
                start = middle + 1;
            }
            // 如果要查找的数值小于中间值
            if (number < num_middle) {
                end = middle - 1;
            }
        }

        if (index == -1) {
            System.out.println("没有找到输入的数字");
        } else {
            System.out.println("输入的数字在第" + (index + 1) + "个");
        }
 
 ｝

通过二分查找算法查找数组里的对象比线性查找算法性能要高很多，特别是当数组很大的时候。