個(gè)人主頁(yè)：仍有未知等待探索_C語(yǔ)言疑難,數(shù)據(jù)結(jié)構(gòu),小項(xiàng)目-CSDN博客

專題分欄：算法_仍有未知等待探索的博客-CSDN博客

目錄

一、引言

二、整數(shù)二分（二分查找）

1、步驟：

2、示例

【問(wèn)題一】求第一個(gè)大于3的數(shù)的位置？

【問(wèn)題二】求第一個(gè)大于等于3的數(shù)的位置？

【問(wèn)題三】求最后一個(gè)小于等于3的數(shù)的位置？

【問(wèn)題四】求最后一個(gè)小于3的位置？

三、浮點(diǎn)數(shù)二分?

一、引言

二分說(shuō)簡(jiǎn)單也簡(jiǎn)單，說(shuō)難也難。簡(jiǎn)單在于思想非常的簡(jiǎn)單，難就難在邊界值的確定上。下面我將進(jìn)行解釋。二分的前提是數(shù)組是有序的，這個(gè)大家應(yīng)該都知道哈。

二、整數(shù)二分（二分查找）

1、步驟：

1. 先找到數(shù)組的左邊界 l 和右邊界? r。
2. 然后確定要查找的數(shù)x 和中間點(diǎn) mid。
3. if（mid <?x）證明 x 在 mid 的右邊，反之在其左邊。
4. 然后進(jìn)行循環(huán)，直到 l >?r的時(shí)候停止循環(huán)。

2、示例

對(duì)于給定一個(gè)數(shù)組【1，2，3，3，7，7，7，8，9】

【問(wèn)題一】求第一個(gè)大于3的數(shù)的位置？

【問(wèn)題二】求第一個(gè)大于3的數(shù)的位置？

【問(wèn)題三】求最后一個(gè)小于等于3的數(shù)的位置？

【問(wèn)題四】求最后一個(gè)小于3的位置？

其實(shí)這些問(wèn)題大差不差，主要是注意一下查找數(shù) x 和 中間數(shù) mid 的關(guān)系

【問(wèn)題一】求第一個(gè)大于3的數(shù)的位置？

#include<stdio.h>
int q[] = { 1,2,3,3,7,7,7,8,9 }, k = 3;//k為查找的數(shù)
int Binary_search(int q[], int l, int r) {
	int i = l - 1, j = r + 1, mid;
	while (i+1 != j) 
	{
		mid = (i + j) >> 1;
		//分界點(diǎn)是小于等于k的在左邊，大于k的在右邊，所以直接返回 j 就是答案
		if (q[mid] <= k)
		{
			i = mid;
		}
		else
		{
			j = mid;
		}
	}
	return j;
}
int main() {
	
	int len = sizeof(q) / sizeof(q[0]);
	int res = Binary_search(q, 0, len - 1);

	printf("%d", res);
	return 0;
}

【問(wèn)題二】求第一個(gè)大于等于3的數(shù)的位置？

#include<stdio.h>
int q[] = { 1,2,3,3,7,7,7,8,9 }, k = 3;//k為查找的數(shù)
int Binary_search(int q[], int l, int r) {
	int i = l - 1, j = r + 1, mid;
	while (i+1 != j) 
	{
		mid = (i + j) >> 1;
		
		if (q[mid] < k)
		{
			i = mid;
		}
		else
		{
			j = mid;
		}
	}
	return j;
}
int main() {
	
	int len = sizeof(q) / sizeof(q[0]);
	int res = Binary_search(q, 0, len - 1);

	printf("%d", res);
	return 0;
}

【問(wèn)題三】求最后一個(gè)小于等于3的數(shù)的位置？

#include<stdio.h>
int q[] = { 1,2,3,3,7,7,7,8,9 }, k = 3;//k為查找的數(shù)
int Binary_search(int q[], int l, int r) {
	int i = l - 1, j = r + 1, mid;
	while (i+1 != j) 
	{
		mid = (i + j) >> 1;
		
		if (q[mid] <= k)
		{
			i = mid;
		}
		else
		{
			j = mid;
		}
	}
	return i;
}
int main() {
	
	int len = sizeof(q) / sizeof(q[0]);
	int res = Binary_search(q, 0, len - 1);

	printf("%d", res);
	return 0;
}

【問(wèn)題四】求最后一個(gè)小于3的位置？

#include<stdio.h>
int q[] = { 1,2,3,3,7,7,7,8,9 }, k = 3;//k為查找的數(shù)
int Binary_search(int q[], int l, int r) {
	int i = l - 1, j = r + 1, mid;
	while (i+1 != j) 
	{
		mid = (i + j) >> 1;
		
		if (q[mid] < k)
		{
			i = mid;
		}
		else
		{
			j = mid;
		}
	}
	return i;
}
int main() {
	
	int len = sizeof(q) / sizeof(q[0]);
	int res = Binary_search(q, 0, len - 1);

	printf("%d", res);
	return 0;
}

三、浮點(diǎn)數(shù)二分?

?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-754955.html

#include<iostream>
using namespace std;
#include<cstdio>
#include<algorithm>
double x;

double max(double x, double y)
{
	return x > y ? x : y;
}

double fBi_search(double l, double r) 
{
	double mid;
	while (r - l > 1e-8) 
	{
		mid = (l + r) / 2;
		if (mid * mid <= x)
		{
			l = mid;
		}
		else
		{
			r = mid;
		}
	}
	return l;
}
int main() 
{
	//求根號(hào)x
	cin >> x;
	cout<<fBi_search(0, max(1, x));
	return 0;
}

到了這里，關(guān)于C/C++ 整數(shù)二分以及浮點(diǎn)數(shù)二分的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！