Java中如何实现二分查找函数?
Java中可以使用递归和循环两种方式来实现二分查找函数，以下分别介绍。
递归实现：
递归实现二分查找函数的基本思想是，每次取区间的中间位置mid，与要查找的元素比较大小，如果mid大于要查找的元素，则在左半边继续查找，否则在右半边继续查找。
具体的实现过程如下：
public static int binarySearch(int[] nums, int target) {
return binarySearch(nums, 0, nums.length - 1, target);
}
private static int binarySearch(int[] nums, int left, int right, int target) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
return binarySearch(nums, left, mid - 1, target);
} else {
return binarySearch(nums, mid + 1, right, target);
}
}
在主函数里，调用了一个私有的递归函数，传入了数组、左右边界值和要查找的目标元素。在递归函数里，首先判断左右边界值是否越界，如果是则直接返回-1。然后取区间的中间位置mid，如果mid等于目标元素，则返回mid。否则，如果mid大于目标元素，说明目标元素在左半边，递归查找左半区间；如果mid小于目标元素，说明目标元素在右半边，递归查找右半区间。
循环实现：
循环实现二分查找函数的基本思想是，每次取区间的中间位置mid，与要查找的元素比较大小，如果mid大于要查找的元素，则在左半边继续查找，否则在右半边继续查找。不断重复这个过程，直到找到目标元素或者整个区间缩小为0为止。
具体的实现过程如下：
public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
在主函数里，使用了一个while循环来不断缩小查找区间的范围。循环条件是，左边界值小于等于右边界值。每次循环，都取区间的中间位置mid。如果mid等于目标元素，则返回mid。否则，如果mid大于目标元素，说明目标元素在左半边，将右边界值缩小到mid-1；如果mid小于目标元素，说明目标元素在右半边，将左边界值扩大到mid+1。不断重复这个过程，直到找到目标元素或者整个区间缩小为0为止。
二分查找函数的时间复杂度为O(log n)，比线性查找的时间复杂度O(n)更加高效。但是前提是，被查找的数组必须是有序的。如果数组无序，则需要先进行排序操作，时间复杂度会更高。