二分查找

查找

二分查找

续：其实也不算有序数组，如果寻找的数在一个区间内，且这个区间的数有序，那么就可以使用二分查找

对于一个有序数组，我们可以采用二分查找，把时间复杂度从O(n) 降到O(log n)，二分是指对于一个有序数组，对于其有序的特性，采用从中间开始查找，同时更新数组的下标，来更快地找到目标值.

代码：

int a[10] ;

for(int i = 0 ; i <= 9 ; i ++)
{
	scanf("%d",&a[i]);
}	

int i = 0 , j = a.size() - 1;

while(i  <=  j)

{

		int mid = (i + j) / 2;

		//对于不同的排序数组，采用不同比较方法和mid的赋值方法，这里以升序数组为例

		if(a[mid] > target) j = mid - 1;

		if(a[mid] < target) i = mid + 1;

		if(a[mid] == target)   {  cout << mid << endl; return ;}

}

续写

写了一道牛客的题

二分[][[B-爱恨的纠葛_2024牛客寒假算法基础集训营6 (nowcoder.com)][B-爱恨的纠葛_2024牛客寒假算法基础集训营6 (nowcoder.com)]

有了一些新的看法

Ac代码

一开始写的时候没想到是二分写了一坨

看了提示之后，选择了面对二分 悲 :(

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

#define ll long long

const int N = 1e5 + 10;

int a[N], b[N];

void solve()
{
	int n, ans = 0x3f3f3f3f;
	
	int idxa = 0, idxb = 0;

	cin >> n;
	for(int i = 0;i < n;i ++) cin >> a[i];

	for(int i = 0;i < n;i ++) cin >> b[i];

	sort(a, a + n);

	for(int i = 0;i < n;i ++)
	{
		int l = 0, r = n - 1;
     
		while(l < r)
		{
		   // mid 取 l 和 r 的中间值
            // 且在更新l 和 r 时，寻找的时 找的是小于等于目标值的最大值
            // 因为l + r是向下取整 所以一直是在找左边界
            int mid = l + r >> 1;
			if(a[mid] >= b[i]) r = mid;
			else l = mid + 1; 
		}

		if(ans > abs(a[l] - b[i]))
		{
			ans = abs(a[l] - b[i]);
			idxa = l;
			idxb = i;
		}

		l = 0, r = n - 1;
		while(l < r)
		{
            // 为啥这儿就变成 l + r + 1 >> 1 了呢
            // 因为向下取整的原因，边界是一直在往左靠的
            // 可能导致死循环
            // 所以需要 + 1
			int mid = l + r + 1 >> 1;
			if(a[mid] <= b[i]) l = mid;
			else r = mid - 1;
		}

		if(ans > abs(a[l] - b[i]))
		{
			ans = abs(a[l] - b[i]);
			idxa = l;
			idxb = i;
		}
	 }
	swap(a[idxa],a[idxb]);

	for(int i = 0;i < n;i ++) cout << a[i] << ' ';
}

int main()
{	
	int t = 1; //cin >> t;
	while(t --)
	solve();
	return 0;
}