欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

记一个二分查找的算法模板(Java版)

程序员文章站 2024-03-20 17:14:46
...

先上代码

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

注意:

  • 为什么mid = start + (end - start) / 2;而不是mid = (start + end) / 2;是为了防止内存溢出。
  • 根据不同的题目要求,可以改写方法体,比如是返回第一个出现的target还是返回最后一个出现的target;返回第一个则如下图所示:
    记一个二分查找的算法模板(Java版)
    返回最后一个则如下图所示:
    记一个二分查找的算法模板(Java版)
  • 为什么不是end = mid ++和start = mid ++;因为题目有可能会要求返回第一个比target大的数值的下标或者第一个比target小的数值下标之类的问题,如果是返回等于target的下标则可以。
  • 为什么while判断条件是start + 1 < end而不是start < end;因为可能会出现死循环,比如start = 1,end = 2,mid = (1 + 2) / 2 =1;然后如果进入到了start = mid,则start和end一直保持不变,程序将会进入死循环中。