二分查找法，要求使用二分查找查处一个数在数组中的索引，如果不存在打印该数组的最后一个元素的下标，如果出现多次，打印下表最大的一个数
- 提问者网友：ミ烙印ゝ
- 2021-07-28 08:28
- 五星知识达人网友：过活
- 2021-07-28 08:46
int a[10001]; // 所在有序数组
int k; // 所找的数
int l,h,m;
l=1, h=len;
while(l<=h){
m=(l+h)/2; // 二分查找
if(a[m]==k){ // 找到，则往后找看是否还有与之相同的的。
int i;
for(i=m+1;i<=h;i++)if(a[i]!=k)break;
cout<<i-1<<endl; // 输出最后一个
return ;
}else
if(a[m]<k)
h=m-1; // 向前找
else
l=m+1; // 向后找
}
cout<<len<<endl; // 没有找到，输出最后一个元素下标
return;
- 1楼网友：雾月
- 2021-07-28 11:59
二分法查找仅对“顺序存储的有序数列”才有效的。基本算法：先取正中间一个数为KEY，然后把待查找值和这个KEY进行比较，确定待查找数在KEY的左边还是右边，，然后再从那一半中查找。
这样效率很高的，呵呵。
- 2楼网友：蓝房子
- 2021-07-28 10:24
int low,high,mid; low=1 ; high=ST.length; while(low<=high){ mid=(low+high)/2; if (key==ST.elem[mid].key) return mid; else if(key<ST.elem[mid].key) high=mid-1; else low=mid+1; }
上面一段代码中的ST.elem[mid].key这些都是需要你自己定义的顺序表中的