Binary search this problem requires the implementation of binary search algorithm.
Function interface definition: position binarysearch (List L, ElementType x); where the list structure is defined as follows:
typedef int Position; typedef struct LNode *List; struct LNode {
ElementType Data[MAXSIZE];
Position Last; / * saves the position of the last element in the linear table * /}; L is a linear table passed in by the user, in which the ElementType element can be compared through >, = =, < and the topic ensures that the incoming Data is incremental and orderly. The function BinarySearch finds the position of X in the Data, that is, array subscript (Note: the element is stored from subscript 1). If found, the index will be returned, otherwise a special failure flag NotFound will be returned.
Sample referee test procedure:
#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; /* Save the position of the last element in the linear table */ };
List ReadInput(); /* The details are not shown. Element is stored from subscript 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; }
/* Your code will be embedded here */ Input example 1:5 12 31 55 89 101 31
Output sample 1:2
Input example 2:3 26 78 233 31
Output sample 2:0
The implementation method is as follows:
Position BinarySearch( List L, ElementType X )
{
int end=L->Last;
int start=1;
int mid=0;
if(L->Data[start]==X)
return L->Data[start];
if(L->Data[end]==X)
return L->Data[end];
// if(L->Data[start]>X)
// return 0;
// if(L->Data[end]<X)
// return 0;
while(1)
{
if((end-start+1)%2==0)
{
mid=start+(end-start+1)/2-1;
if(L->Data[mid]==X)
return mid;
else if(X<L->Data[mid])
{
if(mid-end==1)
return 0;
end=mid;
}
else
{
if((end-mid)==1)
return 0;
start=mid;
}
}
else
{
mid=start+(end-start)/2;
if(L->Data[mid]==X)
return mid;
else if(X<L->Data[mid])
{
if((mid-end)==1)
return 0;
end=mid;
}
else
{
if((end-mid)==1)
return 0;
start=mid;
}
}
}
}