二分搜索

crazyjums

发布于：Nov 10, 2020

次浏览

1 时间复杂度

二分查找的思想很简单，前提是数组是有序的，查找的时间复杂度是$O(logn)$。利用三个指针，分别指向数组的头部、中间和尾部，如果待查找的元素$target$在数组的前半部分，则跳转到前半部分查找，如果在后半部分，则跳转到后半部分进行查找，当头部的值大于尾部指针的值时，则表示查不到。

2 关键代码

public boolean binarySearch(int []nums, int  target){
    int l = 0, r = nums.length-1;
    while(l<=r){
        int mid = l + (r-l)/2;
        if(nums[mid] == target)
            return true;
        else if(nums[mid] < target)//到后半部分查找
            l = mid + 1;
        else
            r = mid - 1;//到前半部分查找  如果第3行中用的是while(l<r)，则此行应该写成开区间，即r=mid;
    }
    return false;
}