# Week 1 programming assignment: binary search

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;

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;
}

}
}
}```

Added by Irksome on Wed, 01 Apr 2020 17:26:03 +0300