image

编辑人: 流年絮语

calendar2025-07-11

message8

visits664

Java版二分查找(折半查找)

分析&回答


/**
 * 二分查找,左右都闭的写法
 * <p>
 * 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。
 * 但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
 * <p>
 * 首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,
 * 如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,
 * 如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
 * 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
 *
 * @param arr    查找对象
 * @param target 目标值
 * @return
 */
public int binarySearch(int[] arr, int target) {
    int start = 0, end = arr.length - 1;

    // 是否取等号,关键看 end 是否可以取到
    while (start <= end) {
        int mid = start + (end - start) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else if (arr[mid] > target) {
            end = mid - 1;  // 此时 end 可以取到,mid 已经判断过,所以要 mid-1
        }
    }

    return -1;
}


public static void main(String[] args) {
    // index     0  1  2  3  4  5  6  7  8  9  10
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int target = 5;
    BinarySearch demo = new BinarySearch();
    System.out.println("Find index in: " + demo.binarySearch(arr, target));
}

反思&扩展

  • 查找条件:有序数组
  • 平均时间复杂度O(㏒n)

喵呜刷题:让学习像火箭一样快速,快来微信扫码,体验免费刷题服务,开启你的学习加速器!

创作类型:
原创

本文链接:Java版二分查找(折半查找)

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。
分享文章
share