二分查找函数
第一种情形
作者：20010211
写一个函数BinarySeach，在包含size个元素的、从小到大排序int数组a里查找元素p。如果找到，则返回元素下标；如果找不到，则返回-1。
复杂度为O(log(n))
int BinarySearch(int a[], int size, int p)
{
int L = 0; //查找区间的左端点
int R = size - 1; //查找区间的右端点
while (L a[mid])
L = mid + 1; //设置新的查找区间的左端点
else
R = mid - 1; //设置新的查找区间的右端点
}
return -1；
}
第二种情形
写一个函数LowerBound，在包含size个元素的、从小到大排序int数组a里查比给定整数p小的、下标最大的元素。 如果找到，则返回元素下标；如果找不到，则返回-1。
复杂度为O(log(n))
int LowerBound(int a[], int size, int p)
{
int L = 0; //查找区间的左端点
int R = size; // 查找区间的右端点
int LastPos = -1; //到目前为止找到的最优解
while (L = p)
R = mid - 1;
else
{
LastPos = mid;
L = mid + 1;
}
}
return LastPos;
}
注意：
在取查找区间正中元素的下标的过程中：
int mid = (L+R)/2;//不建议采用这个方法
int mid = L+(R-L)/2;//为了防止(L+R)过大溢出
作者：20010211
相关文章
Eva
2020-05-17
Tallulah
2023-07-20
Bea
2023-07-20
Ianthe
2023-07-20
Lani
2023-07-20
Thirza
2023-07-20
Rhoda
2023-07-20
Tesia
2023-07-20
Ursula
2023-07-20
Edana
2023-07-20
Dabria
2023-07-20
Paula
2023-07-20
Peony
2023-07-20
Rayna
2023-07-20
Fawn
2023-07-21
Tia
2023-07-21
Victoria
2023-07-21
Olathe
2023-07-21