c++ - 用二分法寻找，而不是停止

Question

当它在其中获得“大”数组时，我对这种方法有疑问。当我输入带有 10 个数字的数组时，它工作正常。但是，如果我插入 1000 万甚至 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

您是否使用了错误的索引和终止条件？

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(i < n );

return -1;

Answer 2

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 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;
}