二分法的四个简单应用是什么,数学二分法简单应用
1.在有序数组中查找一个元素，并输出它的下标。
//在有序数组中查找元素
#包含stdio.h
int main()
{
int arr[]={ -1，2，4，5，7，8，9，11 }；
int SZ=sizeof(arr)/sizeof(arr[0])；
int left=0，n；
int right=SZ-1；
scanf(%d ，n)；
while(左=右)
{
int mid=left(右-左)/2；
if (arr[mid] n)
{
右=中1；
}
else if (arr[mid] n)
{
左=中1；
}
其他
{
Printf(找到，元素下标是%d\n ，mid)；
打破；
}
}
如果(左/右)
{
Printf(找不到元素\ n )；
}
返回0；
}
2.搜索有序二维数组——在二维数组中，每行从左到右按升序排序，每列从上到下按升序排序。输入一个数字以确定二维数组是否包含该元素，如果包含，则输出其下标。
将目标元素与右上角的元素进行比较。如果目标元素小于右上角元素，则小于右上角元素所在列的所有元素；如果目标元素大于右上角的元素，则它大于右上角的元素所在行中的所有元素。
//2.二维数组查找
#包含stdio.h
int main()
{
int arr[4][4]=
{ 2 ,3 ,4 ,5,
6 ,7 ,8 ,9,
10,11,12,13,
14,15,16,17 };
int row=0；
int col=3，n；
scanf(%d ，n)；
而(n！=arr[row][col]row=0 row 4 col=0 col 4)
{
if(数组[行][列] n)
{
col-；
}
其他
{
排；
}
}
if (n==arr[row][col])
{
Printf (found，元素下标为%d %d\n ，行，列)；
}
其他
{
Printf(找不到元素\ n )；
}
返回0；
}
3.寻找无序数组的局部最小值——寻找一个无序数组中的任意局部最小值，并且数组中相邻的两个元素不相等。
#包含stdio.h
int Check(int sz，int arr[])
{
int left=0；
int right=SZ-1；
if (arr[left] arr[left 1])
{
向左返回；
}
否则if (arr[right] arr[right - 1])
{
向右返回；//判断两端
}
Else//用二分法判断中间
{
while(左=右)
{
int mid=left(右-左)/2；
if((arr[mid]arr[mid-1])(arr[mid]arr[mid 1]))
{
返回mid
}
else if(arr[mid]arr[mid-1]arr[mid]arr[mid 1])
{
左=中1；
}
else//(arr[mid]arr[mid-1]arr[mid]arr[mid 1]) (arr[mid]arr[mid-1]arr[mid]arr[mid 1])
{
右=中1；
}
}
}
}
int main()
{
int arr[]={ 9，8，9，7，5，2，3，7 }；
int SZ=sizeof(arr)/sizeof(arr[0])；
int ret=Check(sz，arr)；
Printf(此数组有局部最小值，此元素下标为%d\n ，ret)；
返回0；
}
四。旋转数组查找-旋转数组的定义：
有序数组nums在下标k(0=k nums.length)旋转，使得数组变成[nums [k]，nums [k 1]，…，nums [n-1]，nums [0]，nums [1]，…，nums [k-1]](例如，[0，1，2，4，5，6，7]在下标3旋转后可能变成[4，5，6，7，0，1，2]。
详细说明：给定一个旋转数组，求它的最小元素并输出它的下标
//旋转数组的查找
//查找旋转数组中的最小元素
#包含stdio.h
int main()
{
int arr[]={ 5，6，1，2，3，4 }；
int SZ=sizeof(arr)/sizeof(arr[0])；
int left=0；
int right=SZ-1；
while(左=右)
{
int mid=left(右-左)/2；
If (arr[mid] arr[right])//在左半部分
{
左=中1；
}
Else if (arr[mid] arr[right])//在右半部分。
{
右=中；//不能mid-1，因为mid很可能是最小值
}
其他
{
Printf(这个数组的最小元素下标是%d\n ，右)；
打破；
}
}
返回0；
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。