java语言：二分查找pta

Java是一种广泛使用的面向对象编程语言，它具有简单、可靠、安全和跨平台等特点。Java语言由Sun Microsystems（现在是Oracle）于1995年推出，它的设计目标是让开发者能够编写一次代码，然后在不同的平台上运行。

二分查找是一种常用的查找算法，也称为折半查找。它适用于有序数组或有序列表中查找特定元素的情况。二分查找的基本思想是将待查找区间不断缩小为两半，直到找到目标元素或确定目标元素不存在。

以下是二分查找的基本步骤：
1. 确定待查找区间的起始位置和结束位置。
2. 计算中间位置，并取得中间位置的元素。
3. 将中间位置的元素与目标元素进行比较。
4. 如果中间位置的元素等于目标元素，则查找成功。
5. 如果中间位置的元素大于目标元素，则在左半部分继续查找。
6. 如果中间位置的元素小于目标元素，则在右半部分继续查找。
7. 重复步骤2至步骤6，直到找到目标元素或确定目标元素不存在。

Java提供了多种实现二分查找的方式，可以使用循环或递归来实现。在Java中，可以使用Arrays类的binarySearch方法来进行二分查找。

相关问题

pta7-1 二分查找java

### PTA 7-1 二分查找 Java 实现

为了实现PTA 7-1中的二分查找功能，下面提供了一个完整的Java方法来执行此操作。该方法接收一个已排序数组以及目标值作为参数，并返回目标值所在的索引；如果没有找到，则返回特定指示符。

public class BinarySearch {
    /**
     * 执行二分查找算法.
     *
     * @param array 输入的有序整数数组
     * @param target 查找的目标数值
     * @return 返回target所在的位置下标, 若不存在则返回 -1
     */
    public static int binarySearch(int[] array, int target) {
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            int mid = (high - low) / 2 + low; // 防止(low+high)/2可能溢出的情况
            int guess = array[mid];
            
            if (guess == target) {
                return mid;
            }
            if (guess > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1; // 表示未找到目标值
    }
}

上述代码实现了标准的二分查找逻辑[^1]。通过不断缩小搜索范围直到定位到目标元素或确认其不在列表内为止。注意这里假设输入的是升序排列的数据集。

pta6-2 二分查找

题目描述：

给定一个有n个元素的升序序列，你要查找其中是否包含给定的某个元素。

输入格式：

第一行包含一个整数n，表示元素个数。

第二行包含n个整数，分别表示各元素的值。

第三行包含一个整数x，表示待查找的元素的值。

输出格式：

如果包含，输出元素所在的下标（下标从0开始），否则输出-1。

输入样例：

5
1 3 4 7 9
7

输出样例：

3

算法1

(二分查找) $O(log n)$

时间复杂度

参考文献

python3 代码

C++ 代码

Java 代码