二分查找

xiaoxiao2021-02-28  43

二分查找是一种静态查找方法,即在查找过程中不添加删除修改元素,必须要求查找的对象是有序的,与查找序列对应的是一个二叉生成树

#include<iostream>

using namespace std; /*数组空间大小*/ #define MAXSIZE 100 typedef int ElementType; /*定义一个指向结构体LNode的指针的数据类型*/ typedef struct LNode *List; /*定义Lnode结构体来表示线性表*/ struct LNode{ ElementType Data[MAXSIZE]; int last;/*线性表元素下标*/ }; /*生成一个空线性表*/ List MakeEmpty(){ List Ptrl; Ptrl=(List)malloc(sizeof(struct LNode));/*为线性表分配内存空间*/ Ptrl->last=-1;/*线性表长度为零*/ return Ptrl; } /*在一个给定线性表中查找一个给定数值*/ int Find(ElementType x,List Ptrl){ int i=0; while(i<=Ptrl->last&&Ptrl->Data[i]!=x)/*没找完整个表或找到给定值继续循环*/ i++; if(i>Ptrl->last) return -1;/*在表中找不到给定值*/ else return i;/*找到给定值*/ } /*在给定线性表的指定位置插入一个元素*/ void Insert(ElementType x,int i,List *Ptrl){ int j;  if ( (*Ptrl)->last == MAXSIZE-1){ cout<<"满了"<<endl; return; }/*线性表已满,无法插入*/ if(i<1||i>(*Ptrl)->last+2){ cout<<"不合法"<<endl; return; }/*插入位置不合法*/ for(j=(*Ptrl)->last;j>=i-1;j--) (*Ptrl)->Data[j+1]=(*Ptrl)->Data[j];/*给定位置后面的元素依次后移一个位置*/ (*Ptrl)->Data[i-1]=x;/*给定位置插入数值*/ (*Ptrl)->last++;/*线性表长度加一*/ return; } /*给定线性表中删除指定位置的元素*/ void Del(int i,List Ptrl){ int j; if(Ptrl->last==-1){ cout<<"空的"<<endl; return; }/*线性表为空*/ if(i<1||i>Ptrl->last+1){ cout<<"不合法"<<endl; return; }/*删除未知不合法,注意,顺序表的删除位置比插入位置少一个*/ for(j=i-1;j<=Ptrl->last;j++) Ptrl->Data[j]=Ptrl->Data[j+1];/*元素前移*/ Ptrl->last--;/*长度减一*/ return; } /*二分查找*/ int BinarySearch(List Ptrl,int x){ int left,right,mid,nofound=-1;/*定义左右中指针并初始化,以及查找失败的返回值*/ left=0; right=(Ptrl->last)-1; while(left<=right){/*只要左指针不超过右指针就一直查找*/ mid=(left+right)/2;/*更新中指针*/ if(x>Ptrl->Data[mid]) left=mid+1;/*待查找值超过中指针和等于中指针的处理结果*/ else if(x<Ptrl->Data[mid]) right=mid-1; else return mid+1;/*查找成功*/ } return nofound;/*失败*/ } int main(){ List L; int n,v[8],k; L=MakeEmpty();/*新建空顺序表*/ for(k=0;k<8;k++){ cin>>v[k]; Insert(v[k],(L->last)+2,&L); }/*通过插入创建一个有八个元素的顺序表*/ n=BinarySearch(L,1000); cout<<n<<endl;/*查找给定值并输出结果*/ return 0; }
转载请注明原文地址: https://www.6miu.com/read-2620011.html

最新回复(0)