[Day14] CH09：寻寻觅觅——二元搜寻法

接下来的这几天，会疯狂运用到上个单元教的阵列，也会碰触一些演算法的概念，而今天要来介绍的是二元搜寻法（Binary Search）。

假若今天给你 n 个数字，要你从中找出其中一个数字，那麽你会怎麽找呢？一个一个找，这样最差的结果就需要找完整个阵列，也就是个 n 个数字，此时时间复杂度就会是 O(n)，这样未免太没效率了。

二元搜寻法

又称二分搜寻法，在已排序好的阵列中，每次会找中间值，将阵列分成比中间值小之元素组成之阵列，和比中间值大之元素组成之阵列，再判断要找的数是大於或小於或等於中间值，若等於则已找到，若小於则从比中间值小之元素组成之阵列寻找，大於则比中间值大之元素组成之阵列寻找，接下来继续将当前阵列一分为二，直到找完或找到。此方法因为每次都将阵列切成一半，因此时间复杂度最差为 O(logn)。

假设已有一个排序好的阵列：

索引值  0,  1,  2,  3,  4,  5,  6,  7,  8
阵列    6, 19, 21, 24, 41, 53, 62, 78, 97

我们要寻找 53，首先看阵列长度为 9，中间值为 41，53 > 41 因此找 5 到 8 元素之阵列。

索引值   5,  6,  7,  8
阵列    53, 62, 78, 97

此时中间值为 62 和 78 中间，随意取 62 或 78，这里我们取 62，53 < 62，所以找第5个元素，刚好剩下最後一个，这样一来就找到了，以下为程序码范例：

import java.util.Scanner;

public class BinarySearch{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int[] arr = {6, 19, 21, 24, 41, 53, 62, 78, 97};
        System.out.print("I want to find: ");
        int findNum = sc.nextInt();
        int position;
        if((position = binarysearch(arr, findNum)) != -1){  //把回传值用 position 接收，再比对是否为 -1
            System.out.printf("%d is in the %d position.%n", findNum, position);
        }
        else{
            System.out.printf("%d isn't in the array.%n", findNum);
        }
        sc.close();
    }

    public static int binarysearch(int[] arr, int num){
        int result = -1;    //预设 -1 为没找到
        int start = 0;
        int end = arr.length - 1;   //长度 - 1 为最後一个索引值

        while(start <= end){
            int mid = start + (end - start) / 2;    //end - start 是为了防止溢位
            if(arr[mid] > num){ //要找的值小於中间值
                end = mid - 1;  //阵列最後一个设为中间值前一个数字
            }
            else if(arr[mid] < num){    //要找的值大於中间值
                start = mid + 1;    //阵列第一个设为中间值後一个数字
            }
            else{   //要找的值等於中间值
                result = mid;
                break;
            }
        }
        return result;
    }
}

除了 while 的写法，还有 for 回圈的写法，大家回家可以试试看，那麽今天就到这里啦！