刷题之二分查找

题目

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
 

入门阶段自然会想到循环遍历获得对应的索引值，但是所耗费的时间内存都较大。根据题目，给定的是一个升序的（有序的）数组，故很容易便能想到二分查找。

        这是普通的循环遍历

class Solution {
    public int search(int[] nums, int target) {
        int i =0;
        while(i<nums.length){
            if(target==nums[i]){
                return i;
            }else{
                i++;
            }

        }
        return -1;
    }
}

        二分法如下:

class Solution {
    public int search(int[] nums, int target) {
        int low=0;
        int high=nums.length-1;
        while(low<=high){
            int mid=(high-low)/2+low;
            int num=nums[mid];
            if(num==target){
                 return mid;
            } else if(num<target){
                low=mid+1;
            }else{
                high=mid-1;
            }       
        }
        return -1;
    }
}

可以看出用时很少。

二分法的原理

在有序数组中使用二分查找，定义查找的范围【low，high】，初始查找是整个数组，每次获取到范围的中点与目标值作比较，如果相等则找到目标，如果目标值大于中点，那么目标值在中点的右侧（假设为升序，倒序在左边）那么重新划定范围【mid+1，high】

mid=（high-low）/2 +low

每次查找都会将范围减半，因此二分查找的时间复杂度是 O(logn)，其中 n 是数组的长度。