寻找与平分，而不是停止

Question

我有这个方法的问题，当它得到“大”的数组。当我用10个数字输入数组时，它工作正常。但是，如果我插入10千位数甚至20的方法永远不会结束，我找不到问题。

int bisection(int el, int* a, int n) 
{ 
    int i = 0; 

    if (n <= 0) 
    { 
     return -1; 
    } 
    else 
    { 

    do 
    { 
     int mid = (i + n)/2; 
     if(el == a[i]) 
     { 
      return i; 
     } 
     else if(el < a[n]) 
     { 
      n = mid - 1; 
     } 
     else if(el > a[i]) 
     { 
      i = mid + 1; 
     } 

    }while(i <= n); 
    } 
} 

我必须找到例如第一个数字，如果我有阵：

indexs: 0 1 2 3 4 5 6 7 8 
elements: 1,1,3,3,3,5,6,7,9 

，我期待为3号我一定要得到这个作为

result: (index) 2 

第一发生。

Answer 1

myusuf的答案几乎是正确的，但它并不总是返回第一次出现的索引。这里是我的建议：

int bisection(int el, int* a, int n) 
{ 
    int i = 0; 
    while(i < n) 
    { 
     // search in range i (inclusive) to n (exclusive) 
     int mid = (i + n)/2; 
     if (el == a[mid] && (mid == 0 || a[mid-1] < el)) 
      return mid; 
     if (el <= a[mid]) 
      n = mid; 
     else 
      i = mid + 1; 
    }; 
    return -1; 
} 

Answer 2

你使用了错误的索引和终止条件吗？

int mid;

do { mid = (i + n)/2; if(el == a[中间] && (mid == 0 || a[mid-1] < el)) //for first occurence { return中间; } else if(el <= a[中间]) { n = mid - 1; } else if(el > a[中间]) { i = mid + 1; } }while(我<Ñ）;

return -1;

Answer 3

也许问题来自于int的最大尺寸。您必须检查您的架构上的sizeof(int)。

对于你的算法，你可以做这样的事情：

unsigned long int bisection(int value, int* vector, unsigned long int size) 
{ 
    unsigned long int left = 0; 
    unsigned long int right = size-1; 
    unsigned long int previous_left; 
    while(left < right) 
    { 
    unsigned long int i = (left + right)/2; 
    if(value < vector[i]) 
     right = i; 
    else 
    { 
     previous_left = left; 
     left = i; 
    } 
    } 
    left = previous_left; 
    while(left < right) 
    { 
    unsigned long int i = (left + right)/2; 
    if(value == vector[i]) 
     right = i; 
    else 
     left = i; 
    } 
    return left; 
}