阶乘、二分查找法及原理--分支循环的简单应用

精选原创

光轮2000 2022-10-18 16:46:56 ©著作权

文章标签 自增二分查找法数组阶乘 文章分类 C/C++ 编程语言 阅读数195

一、计算n的阶乘

思路分析：想要计算n的阶乘，即1*2*3*...*（n-1）*n，那么不难想到要引入一个自增变量，由自增变量又可以联想到要使用循环实现变量自增，只需要让这个变量每次自增的值相乘即可，这个每次相乘的值需要储存到一个变量中，利用这变量来实现前一次自增和本次相乘的目的，于是代码可以写为

#include <stdio.h>
int main()
{
int i = 1;
int s=1;
int n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
s*=i;
printf("%d ",s);
}
return 0;
}

二、计算1！+2！+...+10！

思路分析：思路和上题基本一致，这次需要再引入一个变量用来储存每次的和，于是代码可以写为

#include <stdio.h>
int main()
{
int i = 1;
int sum=0;
int ret=1;
for(i=1;i<=10;i++)
{
ret*=i;
sum+=ret;
printf("%d ",sum);
}
return 0;
}

三（二分查找法）、在一个有序数组中查找具体的某个数字n。编写int binsearch（int x，int v[],int n）;功能：在v[0]<=v[1]<=v[2]<=...<=v[n-1]的数组中查找x

思路分析：题目要求是要在有序数组中查找数字，这里举一个简单的例子，主要引入二分查找法，也叫做折半查找法，这种思想方法很重要。

int arr[]={1,2,3,4,5,6,7,8,9,10};
//下标分别为0,1,2,3,4,5,6,7,8,9
int k = 7;

有这样一个有序数组，我要查找7这个元素，它的下标为6，当然可以一个个访问数组的元素，然后找到你最终想要的元素，但是当基数庞大时，这种方法效率并不高，现在引入一种新的查找方法：二分查找法。顾名思义，二分查找法就是按照你想要的元素将区间一次次等分，最终锁定这个元素的区间，此方法即为二分查找法，查找一次肯定是达不到目的的，所以要使用循环语句，那么循环的判断条件是什么呢？循环的主体又是什么呢？

进一步思考，我在这里引入两个变量，分别是left和right，它们分别代表着左下标和右下标，左下标的初始值为0，在未知数组元素个数的时候右下标的初始值可以为sizeof（arr）/sizeof（arr[0]）,引入变量mid代表这两个下标的中间值。

int left = 0;
int right = sizeof(arr)/sizeof(arr[0])-1;
int mid = (left + right)/2;

当我将某个区间分开时，mid会产生一个新的下标，用arr[mid]代表的数跟我要找的元素比较，如果是arr[mid]大，说明目标元素在mid的左边，那么我们可以保持左下标不变，让新的右下标变成mid-1

if(arr[mid]>k)
{
right = mid - 1;
}

那如果是arr[mid]小，说明目标元素在区间的右边，此时我们可以保持右下标不变，让新的左下标变成mid+1

else if(arr[mid]<k)
{
left = mid + 1;
}

如此以来，我们就可以反复执行这个程序，最终锁定区间

else
{
printf("找到了，下标是：%d\n",mid);
}

可是回到刚才的问题上：循环的判断条件是什么呢？该怎么样让它进入循环呢？

有没有这么一种可能，你要查找到这个元素，在这个数组中根本就不存在，当这个区间缩小到可以确定这个元素的时候（如果有这个元素的话），左下标和右下标都已缩小或扩大到到极限，由于该数组中根本就没有这个元素，导致左下标继续往右扩大，右下标继续往左缩小，那么会出现什么情况呢？那就会导致这个程序无法继续往下执行，想到这里，我们就不难想出循环判断的条件了，那就是左下标一定要小于右下标

while(left<right)

当不满足这个循环条件时，跳出循环，打印not found

所以完整的代码为

#include <stdio.h>
int main()
{
int k = 7;
int arr[]={1,2,3,4,5,6,7,8,9,10} ;
int sz = sizeof(arr)/sizeof(arr[0]);
int left = 0;
int right = sz - 1;
while(left<=right)
{
int mid = (left+right)/2;
if(arr[mid]>k)
{
right = mid - 1;
}
else if(arr[mid]<k)
{
left = mid+1;
}
else
{
printf("找到了，下标是：%d\n",mid);
break;
}
}
if(left>right)
{
printf("not found");
}
return 0;
}

阶乘、二分查找法及原理--分支循环的简单应用

阶乘、二分查找法及原理--分支循环的简单应用

Recommend

Java实现二分查找算法

数据结构与算法：二分查找

面试官，我会写二分查找法了！对，没有 bug 的那种！

实现 sqrt(x)：二分查找法和牛顿法

二分查找及对应的几道经典题目

二分查找及其变种算法

如何运用二分查找算法

”二分查找“算法的时间复杂度

二分查找的简单理解 - 程序员翔仔

【洛谷 P2249】【深基13.例1】查找（向量+二分查找+循环）

About Joyk