学习心得:二分查找

二分查找

基础:查找元素是否出现

#include <stdio.h>
int main() {
    int a[10]={0,1,1,3,4,5,6,7,8,9},int x;
    scanf("%d",&x);
    int l=0,r=9,count=0;
    while(l<=r){
        int m=(l+r)/2;
        if(a[m]==x){
            count=m;
            break;
        }
        if(a[m]>x){
            r=m-1;
        }
        if(a[m]<x)
            l=m+1;
    }
    printf("%d",count);
    return 0;
}

高级：查找元素出现次数

当你需要找到目标元素的第一个和最后一个出现位置时，你可以通过稍作修改来实现。以下是一个引导你思路的步骤：

1. 找到第一个出现位置：
   • 使用标准的二分查找算法找到目标元素。
   • 如果找到目标元素，检查它的前一个元素是否也是目标元素，如果是，则继续在左侧搜索，否则，当前位置就是第一个出现位置。
2. 找到最后一个出现位置：
   • 同样使用标准的二分查找算法找到目标元素。
   • 如果找到目标元素，检查它的后一个元素是否也是目标元素，如果是，则继续在右侧搜索，否则，当前位置就是最后一个出现位置。
3. 处理未找到的情况：
   • 如果在第一步找到第一个出现位置时未找到目标元素，或者在第二步找到最后一个出现位置时未找到目标元素，表示目标元素不存在。

#include<stdio.h>
#include<stdlib.h>
void swap(int *m,int *n){
    int temp=*m;
    *m=*n;
    *n=temp;
}
void sort(int n,int a[n],int l,int r){
    if(l<r) return;
    int key=a[0],ll=l,rr=r;
    while(ll!=rr){
        while(key<=a[rr]&&ll<rr) rr--;
        while(key>=a[ll]&&ll<rr) ll++;
        swap(&a[ll],&a[rr]);
    }
    swap(&a[l],&a[ll]);
    sort(n,a,l,ll-1);
    sort(n,a,ll+1,r);
}
int search(int n,int a[n],int key){
    int l=0,r=n-1;
    while(l<=r){
        int m=(l+r)/2;
        if(a[m]==key){
            int rec1=m,rec2=m;
            while(rec1!=0&&a[rec1-1]==key){
                rec1--;
            }
            while(rec2!=n-1&&a[rec2+1]==key){
                rec2++;
            }
            return rec2-rec1+1;
        }
        if(a[m]<key){
            l=m+1;
        }
        if(a[m]>key) {
            r=m-1;
        }
    }
    return -1;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int *a=(int *)calloc(n,sizeof(int));
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int l=0,r=n-1;
    sort(n,a,l,r);
    while(m--){
        int x;
        scanf("%d",&x);
        int count=search(n,a,x);
        if(count==-1){
            printf("0");
        }else{
            printf("%d\n",count);
        }
    }
    free(a);
    return 0;
}

bsearch函数(<stdlib.h>)

bsearch常与qsort函数联合使用。bsearch查找成功返回指向该元素的指针。

4个参数:

key 指向要查找的元素

base 指向进行查找的数组

num 数组中元素的个数

size 数组中每个元素的大小，一般用*sizeof()*表示

cmp 比较两个元素的函数，定义比较规则。需要注意的是，查找数组必须是经过预先排序的，而排序的规则要和比较子函数cmp的规则相同。

1. 整型

int cmp(const void *a, const void *b){
	return *(int *)a - *(int *)b;//升序
//	return *(int *)b - *(int *)a;//降序
}

2. 浮点型

需要注意浮点数会存在精度损失的问题，所以我们需要通过比较，来返回1或-1，以确定是增序还是降序。

int cmp(const void *a, const void *b){
	return ((*(double *)a - *(double *)b)>0?1:-1);//升序
//	return ((*(double *)a - *(double *)b)<0?1:-1);//降序
}

3. 字符型

int cmp(const void *a, const void *b){
	return *(char *)a - *(char *)b;//升序
//	return *(char *)b - *(char *)a;//降序
}

4. 字符串型

   int cmp(const void *a, const void *b){
   	return strcmp((char *)a, (char *)b);//升序
   //	return strcmp((char *)b, (char *)a);//降序
   }

5. 字符串指针数组

int cmp(const void *a, const void *b){
	return strcmp(*(char **)a, *(char **)b);//升序
//	return strcmp(*(char **)b, *(char **)a);//降序
}

6. 结构体

//sample 1
struct node{
	int id;
}s[100]; 
int cmp(const void *a, const void *b){
	struct node *aa = (node *)a;
	struct node *bb = (node *)b;
	return ((aa->id)>(bb->id))?1:-1;//升序
//	return ((aa->id)>(bb->id))?-1:1;//降序
}
//sample 2
struct node{
	int id;
	char data;
}s[100]; 

int cmp(const void *a, const void *b){
	struct node *aa = (node *)a;
	struct node *bb = (node *)b;
	if(aa->id == bb->id)//若id相同，按照data排序 
		return aa->data - bb->data;
	else//否则按照id排序 
		return aa->id - bb->id;//升序
}