上海跨境电商网站制作,电子商务成功的网站,如何做网站效果更好,江岸区网站公司二分查找(折半查找)#xff1a; 从有序序列中找到给出的要查询的数字。 原理是#xff1a;首先把一个有序序列中间位置的值与要查找的数比较#xff0c;若相等则找到了有序序列中的此数#xff1b;否则比较两者的大小#xff0c;若前者大#xff0c;则把有序序列的中间…二分查找(折半查找) 从有序序列中找到给出的要查询的数字。 原理是首先把一个有序序列中间位置的值与要查找的数比较若相等则找到了有序序列中的此数否则比较两者的大小若前者大则把有序序列的中间位置以前的元素都去掉余下的元素组成一个新的有序数列继续上一步的操作直到找到为止若后者大则把有序数列中间位置以后的元素都去掉余下的元素组成一个新的有序数列继续第一步的操作直到找到为止。若所有元素都与要找的数不同则说明该有序序列中没有要找的数。 优点是比较次数少查找速度快平均性能好其缺点是要求待查表为有序表且插入删除困难。因此折半查找方法适用于不经常变动而查找频繁的有序列表。 具体过程可以参照下图 根据以上概念写出代码
#includestdio.hint *binsearch(int *arr, int n, int se)
{int left 0;int right n;int mid 0;while (left right) //防止有些数没有机会与所输入的数比较{mid left (right - left) / 2;//防止left 与 right 直接相加后溢出//这儿可以用右移运算符代替 /2 因为右移效率高//mid (left right) ((right ^ left)1);与上一句代码的作用相同(left right)作用是把left与right对应位相同的数加起来除2 ((right ^ left)1)right ^ left)把left和right对应位不同时的数加起来1把加起来的这个数除2。综合所得这句代码的作用是把left和right加起来除2.if (arr[mid] se){return arr mid;}else if (se arr[mid]){left mid 1;}else{right mid - 1;}}return NULL; //当找到数时返回其在数组中的下标未找到时返回负值
}int main()
{int num[11] { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 }; //折半查找的数组必须是有序的int key 0;int *ret 0;int size sizeof(num) / sizeof(num[0]);printf(Please enter a number);scanf(%d, key);ret binsearch(num, size, key);printf(%d\n, *ret);system(pause);return 0;
}
再次声明待查找的序列必须是有序的才行。 程序中需要注意的几个点是 1、自定义二分查找函数的返回值 怎样设定返回值可以合的反应出找到了该数并能确定他在有序序列中的位置或者未找到该数。我用的方法是返回下标。因为我的有序序列是一个数组所以当找到了该数时返回该数在数组中的下标即可确定该数在数组中的位置没有找到也很好处理因为下标都是非负数所以若是没有找到则返回一个负数。 2、while的循环条件 3、mid的值不要写成 mid (left right ) / 2 ;因为可能在left 与 right 相加的过程中发生溢出
因为left 和 right都是int型是有范围的(32字节)若是left 和 right都是很大的数接近于int能表示的最大数字那么两数相加后就会溢出因此用一个较为保险的方法—-mid left right-left/ 2.
以上使用数组下标的方式实现的现在介绍一种用指针实现的方法。
int *binsearch(int *start, int count, int num)
{int *end start count - 1;while (start end){int *mid start (end - start) / 2;if (*mid num){return mid;}else if (*midnum){if (*(mid - 1) *(mid 1)){start mid 1;}else{end mid - 1;}}else{if (*(mid - 1) *(mid 1)){end mid - 1;}else{start mid 1;}}}return NULL;
}
这个代码是不考虑数组的排序方式的不管数组是从大到小排序还是从小到大排序都能解决。
很简单的几十行代码就完成了。
