二分查找及其变形
程序员文章站
2022-07-12 09:35:42
...
最基本的二分查找模版:
在有序数组A中查找key,如果找到,返回位置索引,否则,返回-1;
int BinarySearch(int A[], int n, int key)
{
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] < key) {
left = mid + 1;
} else if (A[mid] > key) {
right = mid - 1;
} else {// A[mid] == key
return mid;
}
}
return -1;
}
变种1:如果A有多个key元素,返回最大的,否则,返回-1
int BinarySearch(int A[], int n, int key)
{
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] < key) {
left = mid + 1;
} else if (A[mid] > key) {
right = mid - 1;
} else {// A[mid] == key
result = mid;
left = mid + 1;//继续查找右半边
}
}
return result;
}
变种2:如果A中有多个key元素,返回最小的,否则,返回-1
int BinarySearch(int A[], int n, int key)
{
int left = 0, right = n - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (A[mid] < key) {
left = mid + 1;
} else if (A[mid] > key) {
right = mid - 1;
} else {// A[mid] == key
result = mid;
right = mid - 1;// 继续查找左半边
}
}
return result;
}
变种3:在有序数组A中,查找出最小的比key大的元素索引。
int BinarySearch(int A[], int n, int key)
{
if (A[n-1] < key)
return -1;
int left = 0, right = n - 1;
while (left != right) {
int mid = left + (right - left) / 2;
if (A[mid] <= key) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
变种4:在有序数组A中,查找出最大的比k小的元素索引。
int BinarySearch(int A[], int n, int key)
{
if (A[0] > key)
return -1;
int left = 0, right = n - 1;
while (left < right-1) {
int mid = left + (right - left) / 2;
if (A[mid] >= key) {
right = mid - 1;
} else {
left = mid;
}
}
if (A[right] < key) {
return right;
} else {
return left;
}
}