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

相关问题

pta7-16 二分查找

### 关于PTA平台第7章第16题二分查找

#### 解题思路

题目要求实现的是经典的二分查找算法，适用于在一个已经按升序排列好的列表中高效地找到特定元素的位置。对于此问题的关键在于理解如何通过不断缩小搜索范围来减少所需比较次数。

具体来说，在每次迭代过程中计算当前搜索区间的中间位置`mid`，并将其对应的值与目标值`X`相比较：

- 如果两者恰好相同，则找到了该元素；
- 若`L->Data[mid]`小于`X`，说明目标可能位于右半部分，因此更新最小边界至`mid + 1`继续搜索；
- 反之则调整最大边界为`mid - 1`以探索左半边区域[^4]。

此外需要注意输入输出的具体格式要求，确保最终结果按照指定方式呈现出来。

#### 代码实现

以下是基于上述逻辑编写的C语言版本的解法示例：

#include <stdio.h>

#define NotFound (-1)

typedef int ElementType;
typedef struct {
    ElementType *Data;
    int Last;
} List;

int BinarySearch(List L, ElementType X){
    int min = 0, max = L.Last, mid;
    while(min <= max){
        mid = (min + max) / 2;
        if(L.Data[mid] == X)
            return mid;
        else if(L.Data[mid] < X)
            min = mid + 1;
        else 
            max = mid - 1;
    }
    return NotFound;
}

// 假设这里有一个main函数用于读取输入数据并调用BinarySearch函数处理后输出结果。

为了满足题目中的特殊输出需求——即在同一行内给出所有查询的结果且不带额外空格或换行符，可以在主程序中适当修改打印语句[^5]。

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]。通过不断缩小搜索范围直到定位到目标元素或确认其不在列表内为止。注意这里假设输入的是升序排列的数据集。