二分查找

学习时间2022.12.11

二分查找

基本概念

• 找到一篇文章二分查找详解，但是我没仔细看，先存在这里

知识点补充

• qsort函数
  • 函数声明：

  void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
  

  • 参数：
    base -- 指向要排序的数组的第一个元素的指针。
    nitems -- 由 base 指向的数组中元素的个数。
    size -- 数组中每个元素的大小，以字节为单位。
    compar -- 用来比较两个元素的函数。
  • compar函数

    //a,b是任意两个数字
    int cmpfunc (const void * a, const void * b)
    {
        //从小到大
        return ( *(int*)a - *(int*)b );
        //从大到小
        //return ( *(int*)b - *(int*)a );
    }
  

  • 实例

    #include <stdio.h>
    #include <stdlib.h>
  
    int values[] = { 88, 56, 100, 2, 25 };
  
    int cmpfunc (const void * a, const void * b)
    {
        return ( *(int*)a - *(int*)b );
    }
  
    int main()
    {
        int n;
  
        printf("排序之前的列表：\n");
        for( n = 0 ; n < 5; n++ ) {
            printf("%d ", values[n]);
        }
  
        qsort(values, 5, sizeof(int), cmpfunc);
  
        printf("\n排序之后的列表：\n");
        for( n = 0 ; n < 5; n++ ) {
            printf("%d ", values[n]);
        }
        
        return(0);
    }
  

代码实现

数据结构

typedef int ElemType;

typedef struct {
	ElemType* elem;//整型指针
	int TableLen;//动态数组元素个数
}SSTable;

函数声明

• 初始化数组

    void ST_init(SSTable &ST, int len){
        ST.TableLen = len;
        //ST.elem = (ElemType*)malloc(sizeof(ElemType) * ST.TableLen);
        ST.elem = (ElemType*)calloc(ST.TableLen, sizeof(ElemType));
        //初始化随机数发生器
        srand(time(NULL));
        //输出0-100的ST.TableLen个随机数
        for (int i = 0; i < ST.TableLen; i++)
        {
            ST.elem[i] = rand() % 100;
        }
    }
  

• 二分查找函数

    int Binary_Search(SSTable ST, ElemType key) {
        int low = 0, high = ST.TableLen - 1, mid;
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (ST.elem[mid] == key)
            {
                return mid;
            }
            else if(ST.elem[mid] > key)
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        return -1;
    }
  

• compare函数

    //用于规定快排是从小到大还是从大到小
    int compare(const void* left, const void* right) {
        //从小到大
        return *(ElemType*)left - *(ElemType*)right;
        //从大到小
        //return *(ElemType*)right - *(ElemType*)left;
    }
  

• 输出数组

    void ST_print(SSTable ST) {
        for (int i = 0; i < ST.TableLen; i++) {
            printf("%3d", ST.elem[i]);
        }
        printf("\n");
    }
  

main函数

int main() {
	SSTable ST;
	int pos;
	ElemType key;
	ST_init(ST, 10);
	ST_print(ST);
	//实现快排
	qsort(ST.elem, ST.TableLen, sizeof(ElemType), compare);
	ST_print(ST);
	printf("请输入需要查找的元素key值：");
	scanf("%d", &key);
	pos = Binary_Search(ST, key);
	if (pos!= -1) {
		printf("您所查找的元素%d的位置为：第%d位\n", key, pos);
	}
	else {
		printf("您所查找的元素不存在\n");
	}
}