二分查找：计算查找的次数

参考视频：

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

题目：

6-16 统计二分查找比较的次数

分数 25

作者 杨嫘

单位 桂林学院

在一个有序表中进行二分查找操作，要求查找元素x，统计查找过程中需要比较的次数。

例如：0 2 4 5 8 9
查找元素8，比较次数为2
查找元素9，比较次数为3
查找元素10，比较次数为3

函数接口定义：

int bi_searchSq(SqList L,ElemType x);

其中L和x都是用户传入的参数。L是顺序表；x是要查找的元素值。函数须返回查找过程中比较的次数。

裁判测试程序样例：

typedef int ElemType; typedef struct SqList{ ElemType data[MAXSIZE]; int len; }SqList; void createSq(SqList *L); //输入函数，具体实现略 void printSq(SqList L); //输出函数，具体实现略 int bi_searchSq(SqList L,ElemType x); int main() { SqList L; createSq(&L); int x; scanf("%d",&x); printf("you find %d times",bi_searchSq(L,x)); } /* 请在这里填写答案 */

输入样例：

6 0 2 4 5 8 9 4

输出样例：

you find 1 times

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

C (gcc)

int bi_searchSq(SqList L,ElemType x){ int count=0; int left=0,right=L.len-1; while(left<=right){ count++; int mid=(right-left)/2+left; if(L.data[mid]==x){ return count; }else if(L.data[mid]<x){ left=mid+1; }else{ right=mid-1; } } return count; }