java实现二分法查找

在计算机领域，二分法也叫折半查找（Binary Search），是一种在有序的数据集合中查找某个特定元素的搜索算法，时间复杂度为O(log n)。将目标值与中间点比较，根据大小关系来确定下一次查找的点，直到找到目标值或确定该值不存在为止。在本文中，我们将探索如何使用Java实现二分法查找。

算法思想

二分法查找采用分治思想，将数据集合划分成两个部分，通过比较中间值和目标值的大小来确定下一步操作，再将剩余部分划分为两部分，依此类推，直到找到目标值或者确定没有该值。

算法步骤

1. 从有序数据集合的中间点开始查找。

2. 如果目标值等于中间点的值，则查找结束；否则执行第3步。

3. 如果目标值小于中间点的值，则在左半部分查找；否则在右半部分查找。

4. 重复以上步骤，直到找到目标值或者确定没有该值。

Java实现

下面提供两种Java代码，一种是普通的递归实现，另一种是迭代实现。

递归实现

```

public static int binarySearch(int[] array, int target, int left, int right) {

if (left > right) {

return -1;

}

int mid = (left + right) / 2;

if (array[mid] == target) {

return mid;

} else if (array[mid] > target) {

return binarySearch(array, target, left, mid - 1);

} else {

return binarySearch(array, target, mid + 1, right);

}

}

```

迭代实现

```

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;

} else if (array[mid] > target) {

right = mid - 1;

} else {

left = mid + 1;

}

}

return -1;

}

```

实现说明

这两种实现有些区别。递归实现需要传入数组、目标值和左右指针，迭代实现则只需要传入数组和目标值。递归实现比较简短，但性能较差，因为每次递归都会在栈中创建一个新的调用栈。迭代实现则比较优秀，因为没有额外的方法调用，也就不需要额外的栈空间。

测试

下面是一个简单的测试，可以使用main方法来调用，测试二分法查找的性能和正确性。

```

int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

int target = 5;

System.out.println(binarySearch(array, target)); // 输出 4

```

总结

以上是Java实现二分法查找的方法，通过对二分法查找的算法思想和实现方式进行分析，我们可以得出结论：二分法查找是一种高效的算法，通过把有序数组分成2个部分，一边查找一边缩小数据范围，遇到重复执行判断然后缩小数据范围，直到找到或者确定不存在目标值。在Java中实现二分法查找，可以使用递归或者迭代的方式进行，迭代方式更为简洁效率更高，递归方式更为直观易懂。本文中提供的代码仅作为示例供读者参考，读者可以根据自己的需要进行修改。