实现Java中的二分查找函数的示例代码
发布时间:2023-07-06 10:37:36
二分查找(Binary search)是一种在有序数组中快速查找某一特定元素的算法。它的基本思想是通过将有序数组分成两个部分,然后确定目标元素可能存在的那个部分,反复迭代直到找到目标元素或者确定目标元素不存在为止。
下面是一个示例代码,实现了在Java中使用二分查找函数查找目标元素的功能:
public class BinarySearch {
public static int binarySearch(int[] array, int target) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
// 目标元素等于中间元素,直接返回索引
if (array[mid] == target) {
return mid;
}
// 目标元素小于中间元素,继续在左侧查找
if (target < array[mid]) {
right = mid - 1;
}
// 目标元素大于中间元素,继续在右侧查找
if (target > array[mid]) {
left = mid + 1;
}
}
// 目标元素不存在,返回-1
return -1;
}
public static void main(String[] args) {
int[] array = {1, 3, 5, 7, 9, 11};
int target = 9;
int result = binarySearch(array, target);
if (result == -1) {
System.out.println("目标元素不存在");
} else {
System.out.println("目标元素位于索引 " + result);
}
}
}
以上代码首先定义了一个 binarySearch 方法,该方法接受一个有序数组和目标元素作为参数,并返回目标元素在数组中的索引(如果存在)。函数通过维护两个指针 left 和 right 来确定当前查找范围。
在 while 循环中,算法首先计算中间元素的索引 mid,然后通过与目标元素进行比较来确定下一步的查找范围。如果目标元素等于中间元素,则直接返回中间元素的索引。如果目标元素小于中间元素,则在左侧查找,将 right 指针更新为 mid - 1。如果目标元素大于中间元素,则在右侧查找,将 left 指针更新为 mid + 1。循环不断迭代直到找到目标元素或者确定目标元素不存在。
在主函数中,我们创建了一个有序数组 array 和一个目标元素 target,然后调用 binarySearch 方法来查找目标元素在数组中的索引。最后根据返回的索引值判断目标元素是否存在,并输出结果信息。
以上就是实现Java中二分查找函数的示例代码。通过使用二分查找算法,我们可以在有序数组中快速定位目标元素,提高查找效率。
