二分查找适用于有序的顺序表
#include "stdio.h"
#include "stdlib.h"
//顺序表的二分查找
typedef int ElementType;
typedef struct
{
int length;
int capacity;
ElementType *array;
} SeqList;
int binarySearch(SeqList list, ElementType k)
{
int low = 0, mid, high = list.length - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (k == list.array[mid])
{
return 1;
}
else if (k < list.array[mid])
{
high = mid - 1; //list.array前半区域
}
else
{
low = mid + 1; //list.array后半区域
}
}
return 0;
}
int main()
{
int aList[] = {3, 66, 78, 99, 102, 111};
SeqList list;
list.length = sizeof(aList) / sizeof(aList[0]);
list.array = (int *)malloc(sizeof(int *) * list.length);
int i = 0;
for (; i < list.length; i++)
{
list.array[i] = aList[i];
}
int a = binarySearch(list, 66);
if (a == 1)
{
printf("已查找到");
}
else
{
printf("未查找到");
}
return 0;
}
