day16

回顾二分查找

思路：

对于一个已经排好序的数组，在该数组中查找指定的元素，将要查找的元素与排好序之后的数组中的中间数值进行比对

如果一致，则直接返回，一次性可以得到要查找元素的下标

如果要查找的元素比中间值大，则在中间元素之后整个数组之前的这后半部分数据中进行再次查找。

如果要查找的元素比中间值小，则在中间元素之前和数字开始之后整个数组的前半部分进行再次查找

如果一次性没有找到，则继续在剩余一般数据中再重复以上操作

直到将整个数组都查找完毕，还没有找的，则直接返回指定值。

package com.saas;

import java.util.Arrays;

public class BinarySearch {

    public static void main(String[] args) {
        int[] nums = {12, 44, 6, 7878 , 55, 77};

        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            System.out.print(num + "\t");
        }
        System.out.println();

        System.out.println(binarySearch(nums, 12));
    }

    public static int binarySearch(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;

        while (left <= right){

            int mid = left + (right - left) / 2;

            if(nums[mid] == target){            // 目标数据与中间数据相等，直接返回中间注解的下标mid
                return mid;
            } else if (nums[mid] < target){     //  目标数据比中间数据大，则取右半部分数据，将left值赋值为mid+1
                left = mid + 1;
            } else {
                right = mid - 1;                //  目标数据比中间数据小，则取左半部分数据，将right值赋值为mid-1
            }
        }

        return -1;
    }
}