顺序表-折半查找

59 阅读 0 评论 39 点赞

我是靠谱客的博主标致舞蹈，最近开发中收集的这篇文章主要介绍顺序表-折半查找，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

/*线性表(a1,a2,a3,...,an)中的元素递增有序且按顺序存储于计算机内。要求设计一个算法，完成
用最少时间在表中查找数值为x的元素，若找到，则将其与后继元素位置相交换，若找不到，则将
其插入表中并使表中元素仍递增有序*/
#include<stdio.h>
#include<stdlib.h>
#define InitSize 10
typedef int ElemType;
typedef struct{
	ElemType *data;
	int length;
}SqList;

bool InitList(SqList &L)
{
	L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
	L.length = 0;
	return true;
}
//折半查找
bool halfFound(SqList &L,ElemType x)
{
	int low = 0,high = L.length-1,mid;
	while(low<=high)
	{
		mid = (low+high)/2;
		if(L.data[mid] == x) break;
		if(L.data[mid]>x)
			high = mid-1;
		if(L.data[mid]<x)
			low = mid+1;
	}
	if(L.data[mid] == x && mid!=L.length-1)
	{
		ElemType temp = L.data[mid];
		L.data[mid] = L.data[mid+1];
		L.data[mid+1] = temp;
	}
	if(low>high)
	{
		for(int i=L.length-1;i>high;--i)
			L.data[i+1] = L.data[i];
		L.data[high+1] = x;
		++L.length;
	}
	return true;
}

bool printList(SqList L)
{
	for(int i=0;i<L.length;++i)
		printf("%d ",L.data[i]);
	printf("n");
	return true;
}

void main()
{
	SqList L;
	InitList(L);
	int a[5] = {1,3,4,5,7};
	for(int i=0;i<5;++i)
	{
		L.data[i] = a[i];
		++L.length;
	}
	printList(L);
	halfFound(L,3);
	printList(L);
}