C经典算法之二分查找法
C经典算法之二分查找法
1.根据key查找所在数组的位置
#include/* key=9; 12345678 arr3，4，5，7，9，11，21，23 low=1mid=(low+high)/2=4high=8; onearr[mid]=7<9;solow=mid+1=5;high=8;mid=(low+high)/2=6 twoarr[mid]=11>9solow=5,high=mid-1=5mid=5; arr[mid]=9==key if(key=10)low=mid+1>high */ intmain(intargc,constchar*argv[]) { intfindByHalf(intarr[],intlen,intkey); intarr[]={3,4,5,7,9,11,21,23}; intlen=sizeof(arr)/sizeof(int); intindex=findByHalf(arr,len,88); printf("index=%d\n",index); return0; } intfindByHalf(intarr[],intlen,intkey){ intlow=0; inthigh=len-1; intmid; while(low<=high){ mid=(low+high)/2; //右边查找 if(key>arr[mid]){ low=mid+1; //左边查找 }elseif(key>arr[mid]){ high=mid-1; }else{ returnmid; } } return-1; }
2.插入一个数，得到其所在数组的位置
#include/* key=9; 12345678 arr3，4，5，7，9，11，21，23 low=1mid=(low+high)/2=4high=8; onearr[mid]=7<9;solow=mid+1=5;high=8;mid=(low+high)/2=6 twoarr[mid]=11>9solow=5,high=mid-1=5mid=5; arr[mid]=9==key if(key=10)low=mid+1>high */ intmain(intargc,constchar*argv[]) { intfindByHalf(intarr[],intlen,intkey); intarr[]={3,4,5,7,9,11,21,23}; intlen=sizeof(arr)/sizeof(int); intindex=findByHalf(arr,len,88); printf("index=%d\n",index); return0; } intinsertByHalf(intarr[],intlen,intkey){ intlow=0; inthigh=len-1; intmid; while(low<=high){ mid=(low+high)/2; //右边查找 if(key>arr[mid]){ low=mid+1; //左边查找 }elseif(key>arr[mid]){ high=mid-1; }else{ //如果arr[mid]==key //就把key插入到这个数的后面 returnmid+1; } } //如果low>high说明key>arr[mid]; //就把key插入到low对应的这个数的位置 returnlow; }
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。