欢迎访问宙启技术站
智能推送

Java函数实现二分查找方法的实现。

发布时间:2023-10-13 19:00:42

二分查找,又称折半查找,是一种高效的查找算法。它的思想是将查找区间不断缩小,通过比较中间元素和目标元素,来确定目标元素的位置。在目标元素等于中间元素时,查找成功;在目标元素小于中间元素时,将查找区间缩小到左半部分;在目标元素大于中间元素时,将查找区间缩小到右半部分。这样不断缩小查找范围,直到找到目标元素或查找区间为空。

下面是一个示例代码,实现了二分查找的功能:

public class BinarySearch {
    /**
     * 使用二分查找算法,在有序数组中查找目标元素的位置
     * @param nums 有序数组
     * @param target 目标元素
     * @return 目标元素的位置,如果不存在则返回-1
     */
    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) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 9};
        int target = 5;

        int result = binarySearch(nums, target);

        if (result == -1) {
            System.out.println("目标元素不存在");
        } else {
            System.out.println("目标元素的位置是:" + result);
        }
    }
}

在上面的代码中,binarySearch方法接受一个有序数组nums和一个目标元素target,返回目标元素在数组中的位置。如果目标元素不存在,则返回-1。

该算法使用了两个指针leftright来表示当前查找区间的左右边界。初始时,左边界为数组的 个元素,右边界为数组的最后一个元素。通过不断二分查找,将查找区间缩小直到找到目标元素或查找区间为空。

在每次迭代中,通过计算中间元素mid的索引来确定下一次的查找范围。如果中间元素等于目标元素,则查找成功,返回中间元素的位置。如果中间元素小于目标元素,则将左边界移到中间元素的右边一位,继续查找右半部分。如果中间元素大于目标元素,则将右边界移到中间元素的左边一位,继续查找左半部分。

最后,如果查找区间为空,说明目标元素不存在于数组中,返回-1。

在示例代码中,我们创建一个有序数组nums和一个目标元素target。然后调用binarySearch方法,得到目标元素在数组中的位置,并将结果打印出来。在本例中,目标元素5的位置是2。如果将目标元素改为8,则会打印出"目标元素不存在"。

二分查找的时间复杂度是O(log n),因为每次查找都将查找区间缩小一半。这使得二分查找成为一种高效的查找算法,适合用于大型有序数组中查找目标元素的位置。