遞歸插入通過二進制搜索

Question

我有一個排序數組，並希望遞歸地找到插入元素的位置。例如。插入值爲3的數組2,4,5,6,7,8,12,35，算法應該返回3必須插入的位置的索引（索引1）。 下面的代碼有時會起作用，有時候它會陷入無限循環。最終，我的大腦感覺像果凍，我要求你的幫助。這是代碼：

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; 

} 

編輯現出工作代碼：

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; 

} 

Answer 1

int mid = l + r/2; 

應該

int mid = (l + r)/2; 

編輯：此外，你可以檢查的說明STL算法lower_bound，它正是你想要的，就像我一樣erstand。基於這方面的一個實現是這樣的：

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：你的代碼有一些錯誤的正常工作，其中包括：在第二行

• 你無法檢查a[mid] == e因爲您要插入的元素可能不存在於數組中。這會導致在幾種情況下返回-1。

• 無限循環產生於計算mid並稍後分配mid+1或mid-1的方式。

• ，因爲你要插入的元素可以等於陣列中的一些元素，你會被錯誤地回來，因爲你比較兩個​​和e < a[mid]。

我建議你看看這個奇妙的post關於二進制搜索。無論如何，下面的算法試圖追蹤更多可能的風格和使用帖子的信息。希望能幫助到你。

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