当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 01-复杂度3 二分查找

01-复杂度3 二分查找

2018年03月11日  | 移动技术网IT编程  | 我要评论

小伙在院子开挖3年:成果赞不绝口,shila,g14高德导航软件

　　这道题是一道函数题，题目给好相应接口让完成该子函数。给定的函数接口和结构体定义如下：

#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; /* 保存线性表中最后一个元素的位置 */
};

Position BinarySearch( List L, ElementType X );

　　可以看出是要完成对用链表存储的一个线性表进行二分查找，完成程序如下：

Position BinarySearch(List L, ElementType X)
{
    Position Left, Right, Mid;
    Left = 1;
    Right = L->Last;
    while(Left <= Right){
        Mid = (Left + Right) / 2;
        if(X > L->Data[Mid])
            Left = Mid + 1;
        else if(X < L->Data[Mid])
            Right = Mid - 1;
        else 
            return Mid;
    }
    return NotFound;
}

　　需要注意的一点是while循环条件需是Left <= Right，否则两者指同一个数时会不进入循环判断就直接认为“NotFound”，导致结果不正确。

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网