设a[0:n-1]是已排好序的数组.请改写二分搜索算法,使得当被搜索元素x不在数组中时,返回小于x的最大元素...

Question

设a[0:n-1]是已排好序的数组.请改写二分搜索算法,使得当被搜索元素x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置.
⊥221[2/3]iddle-1和middle+1的元素区间中.所以只要每次二分时预存储这两个值就可以了.不知道对不对？？ pedoc: 9077732

Answer 1

小于x的最大元素在x的左边（x不存在时），大于x的最小元素在x的右边（x不存在时）；所以比较到最后，如果找到x，则输出x的位置，没找到x时，返回最后的位置的左和右位置。如题的代码如下：

include <stdio.h>
int main(){
int ip[100],n,key,i,mid,lt=0,rt,fg=0;
printf("请输入数组长度：");
scanf;
printf("请输入已排序的数组：");
for(i=0;i<n;i++)
scanf("%d",ip+i);
printf("请输入待查找数：");

扩展资料：

二分法算法

当数据量很大适宜采用该方法。采用二分法查找时，数据需是排好序的。假设数据是按升序排序的，对于给定值key，从序列的中间位置k开始比较，如果当前位置arr[k]值等于key，则查找成功；

若key小于当前位置值arr[k]，则在数列的前半段中查找,arr[low,mid-1]；若key大于当前位置值arr[k]，则在数列的后半段中继续查找arr[mid+1,high]，直到找到为止,时间复杂度为O(log(n))。

Answer 2

能写的太少详见我博客,我发在那里了
你说的有点小问题,是用low high求结果的
且每个函数只能返回一个值

小于x的最大索引
return high;
大于x的最小索引
return low != array.length ? low : low + 1;

参考资料：http://hi.baidu.com/dyevis/blog