二分查找(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