欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

7折半查找法

程序员文章站 2024-03-19 14:44:10
...

题目
线性表(a1,a2,a3…an)中的元素递增有序且按顺序存储于计算机内。
要求,设计一个算法,完成用时最少时间在表中查找数值为x的元素,若找到,则将其与后继元素位置相交换,若找不到
则将其插入表中并使表中元素任递增有序

算法思想:顺序存储的线性表递增有序,可以顺序查找,也可以折半查找。题目要求“用最少的时间在表中查找数值为X的元素”
应该用折半查找

#include<stdio.h>
typedef int ElemType;

void SearchExchangeInsert(ElemType A[] ,ElemType x,ElemType n){//n代表数组元素个数 
	int low = 0,high=n-1,mid;//low和high指向顺序表下界和上界的下标
		while(low<=high) {
			mid = (low+high)/2;//找中间位置
			if(A[mid]==x)break;//找到x,退出循环
			else if(A[mid]<x) low = mid+1;//到中点mid的右边部分去查
			else high = mid-1;//到mid的左边部分去查 
		} 

		//下面两个If只会执行一个
		if(A[mid] == x && mid!=n-1){
			//若最后一个元素与x相等,则不存在与其,后继交换的操作
			ElemType t;
			t=A[mid];
			A[mid]=A[mid+1];
			A[mid+1]=t; 
		} 
		if(low>high){//查找失败,插入元素 
			int i;
			for(i=n-1;i>high;i--) A[i+1] = A[i];//后移元素
			A[i+1]=x;//插入元素 
		} 
	}

折半查找法
找x
找到数组A下标的上下界low和high
当low<=high时
计算出mid=(low+high)/2;


若A[mid]符合,直接返回


若x<mid,说明,x比mid小。x在A[mid]的左边,使high=mid-1;继续循环
low--------x------------mid--------------high
||
\/
low--------x-------high-----mid-------------


若mid<x,说明,mid比x小。x在A[mid]的右边,使low=mid+1;继续循环
low--------------mid----------x----------high
||
\/
-------------mid–low---------x----------high