binarySearch在java中如何使用

二分查找算法简介

二分查找算法是一种在有序列表中查找特定元素的有效算法。该算法的基本思想是将有序列表分成两个部分，取中间元素与目标元素进行比较，如果相等则返回位置，如果目标元素小于中间位置的元素，说明目标元素在左侧部分，反之则在右侧部分。通过不断对两个部分进行二分查找，直到找到目标元素或者列表中没有元素为止。

二分查找算法的实现

在Java中，可以采用循环或者递归的方式实现二分查找算法。

使用循环实现二分查找算法

public int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

上述代码使用循环方式实现了二分查找算法。首先定义左边界left为0，右边界right为数组长度减1。然后在每次循环中计算中间位置mid，并与目标元素进行比较。如果相等则返回mid，如果目标元素小于中间位置的元素，则将右边界right更新为mid-1，否则将左边界left更新为mid+1。循环继续直到找到目标元素或者左边界大于右边界为止，此时返回-1表示目标元素不存在于数组中。

使用递归实现二分查找算法

public int binarySearch(int[] arr, int target, int left, int right) {
    if (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            return binarySearch(arr, target, mid + 1, right);
        } else {
            return binarySearch(arr, target, left, mid - 1);
        }
    }
    
    return -1;
}

上述代码使用递归方式实现了二分查找算法。递归函数接收数组、目标元素以及左右边界参数。在每次递归中，计算中间位置mid，并与目标元素进行比较。如果相等则返回mid，如果目标元素小于中间位置的元素，则在左半部分数组继续递归查找，否则在右半部分数组继续递归查找。递归终止条件为左边界大于右边界，此时返回-1表示目标元素不存在于数组中。

总结

二分查找算法在有序列表中查找元素具有高效性能，时间复杂度为O(log n)。在Java中，可以使用循环或者递归的方式实现二分查找算法。循环方式通过不断更新左右边界进行迭代查找，递归方式通过递归调用函数进行分治查找，两种方式在效果上是等价的，具体使用哪种方式取决于个人偏好。通过掌握二分查找算法的实现方式，可以在需要查找特定元素的有序列表中快速定位目标位置。