二分法（Binary Search）学习

二分法，顾名思义，就是对半划分，那怎么进行对半划分呢？

二分法的基本思路，首先初始化左右两个指针，分别指向数组的第一个元素和最后一个元素，然后在每次迭代中计算中间位置mid，并将目标元素与中间元素进行比较。如果中间元素等于目标元素，则直接返回中间位置mid；如果中间元素小于目标元素，则在右半部分继续查找；如果中间元素大于目标元素，则在左半部分继续查找。重复以上步骤，直到找到目标元素或左右指针重合。
选取一个二分法的使用场景，在一个有序的列表中找到一个目标数，返回目标元素在数组中的索引，如果目标元素不存在于数组中，则返回-1。
定义一个类型为 Integer 类型的数组 ， 在本次我们要寻找的目标值 target = 8

        int[] nums = new int[]{1, 2, 4, 6, 8, 10};

在这个数组中，left 和 right 分别为左右边界

   public static int getTarget(int[] nums, int target) {
        // 左边界
        int left = 0;
        //右边界
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            //如果中间元素小于目标元素，则在右半部分继续查找
            if (target > nums[mid]) {
                left = mid + 1;
            } //如果中间元素大于目标元素，则在左半部分继续查找
            else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

程序输出元素所在位置

其实中间位置的选择是有讲究的，有人会问，为啥不是 (left + right)/2 呢。可以试一试，如果使用 (left + right)/2和(right - left)/2 会在程序中陷入死循环

画图解释 mid
所以mid的值一定要在新的left边界加上中间的值，即 int mid = left + (right - left) / 2