无聊送分贴。找错解决思路

无聊送分贴。。。找错
好久没发帖了。。。
谁先到先得。。。

C/C++ code

#include  <iostream> 
 #include  <iomanip> 
  
 using namespace std; 
  
 int binary(int *arr, int size, int number) 
 { 
     if(arr[size/2]  < number) 
        return binary(&arr[size/2], size - size/2, number); 
     else if(arr[size/2]>number) 
        return binary(arr, size - size/2,number); 
     else return size/2; 
 } 
  
 int main() 
 { 
     int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12}; 
     cout < <binary(arr, sizeof(arr)/sizeof(int), 2); 
     return 0; 
 } 
 

[解决办法]
好早啊，那我就当仁不让了
[解决办法]
楼主难道是通宵写这个折半查找，很兴奋？
[解决办法]
楼主
这个程序的如果返回值是数组下标的话必然是错的，
因为每次递归调用size的值会被减半，若第一次查找时那个值的位置不是在size / 2;处
则后面的递归调用的下标返回值全部乱掉
[解决办法]

C/C++ code

#include <iostream>#include <iomanip>using namespace std;int binary(int *arr, int size, int number){    if(arr[size/2] < number)       return binary(&arr[size/2], size - size/2+1, number);    else if(arr[size/2]>number)       return binary(arr, size - size/2+1,number);    else return size/2;//最后的这里肯定是1的，因为你的数组长度一直在变的}int main(){    int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12};    cout<<binary(arr, sizeof(arr)/sizeof(int), 11);    return 0;}
[解决办法]
建议LZ画图分析一下。。。。
[解决办法]
探讨

楼主
这个程序的如果返回值是数组下标的话必然是错的，
因为每次递归调用size的值会被减半，若第一次查找时那个值的位置不是在size / 2;处
则后面的递归调用的下标返回值全部乱掉

[解决办法]
楼主难道通宵写这个。。。
[解决办法]
明显有bug嘛，当你查数组后半部分的时候返回的值都是1.因为你的size一直在减小的，到最后就是2了，除以2自然是1了。
[解决办法]
改成这个样子。
C/C++ code
#include <iostream>using namespace std;int binary(int *arr, int left,int right, int number){    if(arr[(left+right)/2]< number)        return binary(arr,(left+right)/2+1,right , number);    else if(arr[(left+right)/2]> number)        return binary(arr,left,(left+right)/2-1 , number);    else        return (left+right)/2;}int main(){    int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12};    cout<<binary(arr, 0,sizeof(arr)/sizeof(int)-1, 12);    return 0;}
[解决办法]
接分，不给你不是人
[解决办法]
jf                   jf
[解决办法]
按9楼改吧，否则你要找的元素如果是在两头按照你写的是没办法找到的。
[解决办法]
顶９楼
[解决办法]
接分！！！
[解决办法]
 else return size/2;  // else  return (left+right)/2;
      


------解决方案-------------------- 
 
一种比较丑陋的实现：
C/C++ code
#include <iostream>using namespace std;int binary(int *arr, int size, int number){    static int index = 0;//增加一个静态变量用于返回正确的下标    //增加递归结束条件，防止栈溢出    if (size <= 0 || ((size == 1) && arr[0] != number))        return -1;    if(arr[size/2] < number)    {        index += size/2;        return binary(&arr[size/2], size - size/2, number);    }    else if(arr[size/2]>number)        return binary(arr, size - size/2, number);    else        return (size/2 + index);    }int main(){    int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12};    cout<<binary(arr, sizeof(arr)/sizeof(arr[0]), 129);    system("pause");    return 0;}
[解决办法]
接点分回去，错误都被人先抢了 

 

查看更多 下一篇