线性查找

线性查找是在数组中从头开始依次向下查找即可，也就是遍历。
很容易理解，缺点是在数据量大且目标数据比较靠后的时候，比较的次数会很多，就会更加耗时。
其时间复杂度为O(n)。

二分查找

二分查找是通过比较数组中间的数据与目标数据的大小来确认目标数据在数组的左边和右边，每比较一次可以排除一般的范围，重复操作到找到目标数据位置。
二分查找的话，需要已经排序好的数组，每次减半查找范围，查找到只剩一个数据的时候结束。
所以其时间复杂度为O(logn)。

Tips:二分查找的模版

模版1

    int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0,right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return -1;
    }

这个是二分查找的最基础和最基本的形式。查找条件可以在不与与元素的两侧进行比较的情况下确定。不需要后处理，因为每一步都检查是否查找到了元素，如果到了末尾，则知道是否找到了该元素。

模版2

    int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0,right = nums.length;
        while (left < right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        if(left != nums.length && nums[left] == target) return left;
        return -1;
    }

这是二分查找的一个变种，用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件。
查找条件需要访问元素的直接右邻居是否满足条件来确定向左还是向右，保证查找空间每一步至少有两个元素，需要进行后处理，当你只剩下一个元素的时候，循环结束，需要评估剩余元素是否符合条件。

模版3

    int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0,right = nums.length-1;
        while (left+1 < right) {
            int mid = left + (right - left)/2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        //  结束条件：left+1 = right
        if(nums[left] == target) return left;
        if(nums[riight] == target) return right;
        return -1;
    }

这是二分查找的另一种独特形式，用于搜索需要访问当前索引及其在数组直接左右邻居索引的元素或者条件。
保证每个步骤中至少需要三个元素，需要进行后处理，当剩下两个元素的时候，循环结束，需要评估其余元素是否符合条件。