首页 > 编程语言 >二分查找及java代码实现

二分查找及java代码实现

时间:2024-12-06 14:03:34浏览次数:14  
标签:二分 java int mid 查找 low 数组 目标值

二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法。它通过比较数组中间元素与目标值来确定目标值所在的范围,然后在这个范围内继续进行二分查找,直到找到目标值或确定目标值不存在。
二分查找的基本步骤:
1.  初始化:设置两个指针,一个指向数组的开始(low),另一个指向数组的结束(high)。
2.  比较中间元素:计算中间位置 mid = low + (high - low) / 2,并比较中间元素与目标值。
3.  调整范围:
•  如果中间元素等于目标值,则查找成功,返回中间位置。
•  如果中间元素小于目标值,则在数组的右半部分继续查找(low = mid + 1)。
•  如果中间元素大于目标值,则在数组的左半部分继续查找(high = mid - 1)。
4.  重复:重复步骤2和3,直到找到目标值或low大于high(表示目标值不在数组中)。
Java代码实现:
public class BinarySearch {
    // 二分查找算法实现
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        
        while (low <= high) {
            // 计算中间位置
            int mid = low + (high - low) / 2;
            
            // 检查中间元素是否是目标值
            if (arr[mid] == target) {
                return mid; // 找到目标值,返回其索引
            }
            
            // 如果中间元素小于目标值,则在右半部分查找
            if (arr[mid] < target) {
                low = mid + 1;
            }
            // 如果中间元素大于目标值,则在左半部分查找
            else {
                high = mid - 1;
            }
        }
        
        // 如果没有找到目标值,返回-1
        return -1;
    }
    
    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int target = 10;
        
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("元素 " + target + " 在数组中的索引为: " + result);
        } else {
            System.out.println("数组中没有元素 " + target);
        }
    }
}

这段代码定义了一个binarySearch方法,它接受一个整数数组和一个目标值作为参数,并返回目标值在数组中的索引。如果目标值不在数组中,则返回-1。main方法提供了一个使用示例。

标签:二分,java,int,mid,查找,low,数组,目标值
From: https://blog.csdn.net/silver687/article/details/144187380

相关文章