📄 binsrch.c
字号:
/*
** BINSRCH.C - Binary search arrays for a key.
**
** Public domain demo by Bob Stout
*/
#include <stdio.h>
#include <stddef.h>
#include "binsrch.h"
#if !(__cplusplus)
/*
** BinSearchI(): Search a int key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchI(int key, int *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchC(): Search a character key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchC(signed char key, signed char *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return Error_;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchB(): Search a byte key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchB(BYTE key, BYTE *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchS(): Search a short key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchS(signed short key, signed short *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchW(): Search a word key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchW(WORD key, WORD *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchL(): Search a long key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchL(signed long key, signed long *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchDW(): Search a double word key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchDW(DWORD key, DWORD *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchF(): Search a float key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchF(float key, float *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
/*
** BinSearchD(): Search a double key
**
** Arguments: 1 - Address to return the key position
** 2 - Key to find
** 3 - Pointer to the beginning of the array
** 4 - Number of elements in the array
**
** Returns: Index if found, else -1
*/
int BinSearchD(double key, double *r, size_t n)
{
int high, i, low;
if (n > 1)
{
for (low = 0, high = n-1; high - low > 1; )
{
i = (high+low) / 2;
if (key == r[i])
return i;
else if (key < r[i])
high = i;
else low = i;
}
if (key == r[high])
return high;
else if (key == r[low])
return low;
else return -1;
}
else if (r[0] == key)
return 0;
else return -1;
}
#else /* C++ */
// See BINSRCH.H for binary search function template
#endif /* C/C++ */
#ifdef TEST
#include <stdlib.h>
#if !(__cplusplus)
#include <stdio.h>
main(int argc, char *argv[])
{
double a1[] = { 1, 3, 17, 39, 66, 67, 88, 111, 222, 333, 345 };
double a2[] = { 1, 3, 17, 39, 66, 67, 88, 111, 222, 333, 345, 678};
double a3[] = { 5, 9, 37 };
double a4[] = { 5, 9, 13 };
double a5[] = { 5, 9 };
double a6[] = { 6 };
double a7[] = { -20, 1, 30 };
double key;
int idx;
while (--argc)
{
key = atof(*(++argv));
if (-1 != (idx = BinSearchD(key, (double *)a1, sizeof(a1) / sizeof(key))))
printf("Key %f found at position %d in a1[]\n", key, idx);
else printf("Key %f not found in a1[]\n", key);
if (-1 != (idx = BinSearchD(key, (double *)a2, sizeof(a2) / sizeof(key))))
printf("Key %f found at position %d in a2[]\n", key, idx);
else printf("Key %f not found in a2[]\n", key);
if (-1 != (idx = BinSearchD(key, (double *)a3, sizeof(a3) / sizeof(key))))
printf("Key %f found at position %d in a3[]\n", key, idx);
else printf("Key %f not found in a3[]\n", key);
if (-1 != (idx = BinSearchD(key, (double *)a4, sizeof(a4) / sizeof(key))))
printf("Key %f found at position %d in a4[]\n", key, idx);
else printf("Key %f not found in a4[]\n", key);
if (-1 != (idx = BinSearchD(key, (double *)a5, sizeof(a5) / sizeof(key))))
printf("Key %f found at position %d in a5[]\n", key, idx);
else printf("Key %f not found in a5[]\n", key);
if (-1 != (idx = BinSearchD(key, (double *)a6, sizeof(a6) / sizeof(key))))
printf("Key %f found at position %d in a6[]\n", key, idx);
else printf("Key %f not found in a6[]\n", key);
if (-1 != (idx = BinSearchD(key, (double *)a7, sizeof(a7) / sizeof(key))))
printf("Key %f found at position %d in a7[]\n", key, idx);
else printf("Key %f not found in a7[]\n", key);
}
return EXIT_SUCCESS;
}
#else /* C++ */
#include <iostream.h>
main(int argc, char *argv[])
{
double a1[] = { 1, 3, 17, 39, 66, 67, 88, 111, 222, 333, 345 };
double a2[] = { 1, 3, 17, 39, 66, 67, 88, 111, 222, 333, 345, 678};
double a3[] = { 5, 9, 37 };
double a4[] = { 5, 9, 13 };
double a5[] = { 5, 9 };
double a6[] = { 6 };
double a7[] = { -20, 1, 30 };
double key;
int idx;
while (--argc)
{
key = atof(*(++argv));
if (-1 != (idx = BinSearch(key, a1, sizeof(a1) / sizeof(key))))
cout << "Key " << key << " found at position " << idx << " in a1[]" << endl;
else cout << "Key " << key << " not found in a1[]" << endl;
if (-1 != (idx = BinSearch(key, a2, sizeof(a2) / sizeof(key))))
cout << "Key " << key << " found at position " << idx << " in a2[]" << endl;
else cout << "Key " << key << " not found in a2[]" << endl;
if (-1 != (idx = BinSearch(key, a3, sizeof(a3) / sizeof(key))))
cout << "Key " << key << " found at position " << idx << " in a3[]" << endl;
else cout << "Key " << key << " not found in a3[]" << endl;
if (-1 != (idx = BinSearch(key, a4, sizeof(a4) / sizeof(key))))
cout << "Key " << key << " found at position " << idx << " in a4[]" << endl;
else cout << "Key " << key << " not found in a4[]" << endl;
if (-1 != (idx = BinSearch(key, a5, sizeof(a5) / sizeof(key))))
cout << "Key " << key << " found at position " << idx << " in a5[]" << endl;
else cout << "Key " << key << " not found in a5[]" << endl;
if (-1 != (idx = BinSearch(key, a6, sizeof(a6) / sizeof(key))))
cout << "Key " << key << " found at position " << idx << " in a6[]" << endl;
else cout << "Key " << key << " not found in a6[]" << endl;
if (-1 != (idx = BinSearch(key, a7, sizeof(a7) / sizeof(key))))
cout << "Key " << key << " found at position " << idx << " in a7[]" << endl;
else cout << "Key " << key << " not found in a7[]" << endl;
}
return EXIT_SUCCESS;
}
#endif /* C/C++ */
#endif /* TEST */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -