通过二进制搜索进行递归插入 [英] Recursive Insert via binary search

问题描述

我有一个排序数组，想递归地找到插入元素的位置.例如.插入值为3的数组2,4,5,6,7,8,12,35，算法应返回必须插入3的位置的索引(索引1).以下代码有时有效，而其他时候则陷入无限循环.最终，我的大脑感觉像果冻一样，我请求您的帮助.这是代码:

I have a sorted array and want to recursively find a position for inserting an element. E.g. an array 2,4,5,6,7,8,12,35 with an insertion value of 3 and the algorithm should return the index of the position where the 3 has to be inserted (index 1). The following code works sometimes, and other times it gets stuck in an infinite loop. Eventually my brain feels like jelly and I ask for your help. This is the code:

private static int insertRec(int[] a, int e, int l, int r) {
    int mid = l + r / 2;
    if (l == r || a[mid] == e) return mid;
    if (e > a[mid]) insertRec(a, e, mid + 1, r);
    if (e < a[mid]) insertRec(a, e, l, mid - 1);
    return -1;

}

使用假定的工作代码进行

Edit with assumed working code:

private static int insertRec(int[] a, int e, int l, int r) {
    int mid = (l + r) / 2;
    if (l == r || a[mid] == e) return mid;
    else if (e > a[mid]) return insertRec(a, e, mid + 1, r);
    else if (e < a[mid]) return insertRec(a, e, l, mid - 1);
    return -1;

}

推荐答案

int mid = l + r / 2;

应该是

int mid = (l + r) / 2;

编辑:此外，您可以检查STL算法的说明 lower_bound 正是您所需要的，据我所知.基于此的实现将是:

EDIT: moreover, you can check the description of the STL algorithm lower_bound which makes exactly what you want, as I understand. A implementation based on this would be like:

int lb(int a[], int last, int val) { // array, len of the array, element to insert
  int it, count, step;
  int first = 0;
  count = (last-first);
  while (count > 0) {
    it = first;
    step = count/2;
    it += step;
    if (a[it] < val) {
      first = ++it;
      count -= step+1;
    } else
      count = step;
  }
  return first;
}

EDIT2 :您的代码存在一些错误，无法正常工作，其中包括:

EDIT2: your code has a few mistakes to work properly, among them:

在第二行的

• 中，您无法检查 a [mid] == e ，因为要插入的元素可能不存在于数组中.在某些情况下，这将导致返回-1.

• in the second line you cannot check if a[mid] == e because the element you want to insert, may not exist in the array. This will cause to return -1 in several cases.

无限循环源于计算 mid 并随后分配 mid + 1 或 mid-1 的方式.

the infinite loop arises from the way of computing mid and later assigning mid+1 or mid-1.

因为您要插入的元素可能等于数组中的某些元素，所以您将返回错误，因为您要比较两个 e>a [mid] 和 e<a [mid] .

because the element you want to insert may be equal to some elements in the array, you will be returning incorrectly, since you compare for both e > a[mid] and e < a[mid].

我建议您看一下有关二进制搜索的这篇奇妙的帖子.无论如何，这是尝试遵循您的样式并使用帖子信息的算法.希望对您有所帮助.

I advice you to take a look at this fantastic post about binary search. In any case, here's the algorithm trying to follow the more possible your style and using the info of the post. Hope it helps.

private static int insertRec(int[] a, int e, int l, int r) {
    int mid = l + (r - l) / 2;
    if (l == r) return l;
    else if (a[mid] < e) return insertRec(a, e, mid+1, r);
    else return insertRec(a, e, l, mid);
}

这篇关于通过二进制搜索进行递归插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！