想问一下有关数据元素查找的问题!

Question

R6-3 二分查找分数 17
全屏浏览题目
切换布局
作者 陈越
单位 浙江大学
本题要求实现二分查找算法。
函数接口定义：

Position BinarySearch( List L, ElementType X );

其中List结构定义如下：
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。
裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    Position P;

    L = ReadInput();
    scanf("%d", &X);
    P = BinarySearch( L, X );
    printf("%d\n", P);

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例1：
5
12 31 55 89 101
31

输出样例1：
2

输入样例2：
3
26 78 233
31

输出样例2：
0

我的代码：
Position BinarySearch( List L,ElementType X ){
    int i;
    int count=0;
    for(i=0;i<L->Last;i++){
        if(L->Data[i]==X){
            return i;
            break; 
        }else{
            count++;
        }
    }
    if(count==L->Last){
        return NotFound;
   }
}

想问我这个代码错在哪儿了？这里我并没有用二分法做到，这个测试点一直不对

Answer 1

解题思路

二分查找算法的基本思想是：将要查找的元素与中间元素进行比较，如果相等，则返回中间元素的下标；如果中间元素比要查找的元素大，则在左半部分继续查找；如果中间元素比要查找的元素小，则在右半部分继续查找。重复这个过程，直到找到要查找的元素或者确定该元素不存在为止。

在本题中，我们可以使用结构体List来表示线性表，其中Last保存线性表中最后一个元素的位置。在函数BinarySearch中，我们先计算出线性表的中间位置Index，然后将要查找的元素与中间元素进行比较。如果相等，则返回中间元素的下标；否则，根据比较结果将查找范围缩小为左半部分或右半部分，并重复这个过程，直到找到要查找的元素或者确定该元素不存在为止。

具体实现细节如下：

计算线性表的中间位置Index。首先计算中间位置的索引值Index = (Last + 1) / 2，其中Last是线性表中最后一个元素的位置。这样计算的原因是，线性表的长度为Last - 1，因此中间位置的索引值应该为(Last + 1) / 2。
将要查找的元素与中间元素进行比较。如果相等，则返回中间元素的下标；否则，如果X > Data[Index]，则说明要查找的元素在右半部分，应该在Index + 1处继续查找；如果X < Data[Index]，则说明要查找的元素在左半部分，应该在Index处继续查找。
如果确定要查找的元素不存在，则返回一个特殊的失败标记NotFound。