当前位置：首页 > web >正文

重温经典算法——二分查找

web 2025/6/22 7:36:09

版权声明

本文原创作者：谷哥的小弟
作者博客地址：http://blog.csdn.net/lfdfhl

在这里插入图片描述

基本原理

二分查找（Binary Search）是一种基于分治策略的高效搜索算法，适用于有序数组，其核心思想是通过重复将搜索区间分成两半：首先取中间元素与目标值比较，若相等则直接返回位置；若目标值小于中间元素，则在左半区间继续搜索；若目标值大于中间元素，则在右半区间继续搜索，直至找到目标值或搜索区间为空（表明目标不存在）。该算法每次比较可将搜索范围缩小一半，时间复杂度为 O(log n)，空间复杂度为 O(1)，具有查找速度快、性能稳定的优点。

代码实现

public class BinarySearch {/*** 二分查找实现* @param arr    有序数组（升序）* @param target 目标值* @return 目标值索引（未找到时返回 -1）*/public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1; // 右闭区间while (left <= right) { // 终止条件：左边界 <= 右边界int mid = left + (right - left) / 2; // 防溢出写法：(left + right) 可能溢出if (arr[mid] == target) {return mid; // 找到目标} else if (arr[mid] < target) {left = mid + 1; // 目标在右半部分} else {right = mid - 1; // 目标在左半部分}}return -1; // 未找到}public static void main(String[] args) {int[] arr = {2, 5, 8, 12, 16, 23, 38, 45, 56};int target = 23;int result = binarySearch(arr, target);if (result != -1) {System.out.println("目标值 " + target + " 的索引为: " + result);// 输出：目标值 23 的索引为: 5} else {System.out.println("目标值不存在");}}
}