pta6-2 二分查找

题目描述：

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

输入格式：

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

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

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

输出格式：

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

输入样例：

5
1 3 4 7 9
7

输出样例：

3

算法1

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

时间复杂度

参考文献

python3 代码

C++ 代码

Java 代码

相关问题

pta6-10 二分查找

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的算法。它的基本思想是将数组分成两部分，然后确定目标元素可能存在的那一部分，并继续在该部分进行查找，直到找到目标元素或者确定目标元素不存在。

具体的二分查找算法如下：
1. 初始化左指针left为数组的起始位置，右指针right为数组的结束位置。
2. 计算中间位置mid，即mid = (left + right) / 2。
3. 比较中间位置的元素与目标元素的大小关系：
- 如果中间位置的元素等于目标元素，则找到目标元素，返回其索引。
- 如果中间位置的元素大于目标元素，则目标元素可能在左半部分，更新右指针right为mid - 1。
- 如果中间位置的元素小于目标元素，则目标元素可能在右半部分，更新左指针left为mid + 1。
4. 重复步骤2和步骤3，直到左指针大于右指针，表示查找结束，目标元素不存在。

二分查找的时间复杂度为O(logn)，其中n为数组的长度。它是一种高效的查找算法，在有序数组中查找元素时非常常用。

pta7-12二分查找

二分查找是一种高效的查找算法，它的前提是待查找的序列必须是有序的。具体实现过程如下：

1.定义一个函数，传入待查找的序列和待查找的元素。

2.定义左右两个指针，分别指向序列的第一个元素和最后一个元素。

3.当左指针小于等于右指针时，执行以下操作：

a.计算中间位置的索引，即(left+right)//2。

b.如果中间位置的元素等于待查找的元素，返回中间位置的索引。

c.如果中间位置的元素大于待查找的元素，将右指针移动到中间位置的左边一个位置。

d.如果中间位置的元素小于待查找的元素，将左指针移动到中间位置的右边一个位置。

4.如果左指针大于右指针，说明待查找的元素不存在于序列中，返回-1。

下面是一个示例代码：

def binary_search(arr, x):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    return -1