二進制搜索和插入排序

我的insertInOrder方法是錯誤的（它向後打印數字列表）。我正在閱讀數字列表，並且我想使用插入排序算法來使用二進制搜索的索引位置以升序排列數字。我不確定如何去解決這個問題，並且非常感謝。二進制搜索和插入排序

static void insertInOrder(int[] arr, int cnt, int newVal) { 

    int index = bSearch(arr, 0, arr.length-1, newVal) ; 
    if (index < 0) { 
     index = -1 - index ; 
    } 
    for (int i = cnt; i >= index+1 ; --i) { 
     arr[i] = arr[i-1]; 
    } 

    arr[index] = newVal; 
} 


public static int bSearch(int[] a, int lo, int hi, int key) { 
    int mid = (lo+hi)/2; 
    if(lo>hi) 
     return -1; 
    else if (a[mid]==key) 
     return mid; 
    else if (a[mid]<key) 
     return bSearch(a, mid+1, hi, key); 
    else 
     return bSearch(a, lo, mid-1, key); 
}

Reading in: 5 13 7 9 21 
Current Output: 21 9 7 13 5 
Desired Output: 5 7 9 13 21

這是insertInOrder在我的主要

int[] arr = new int[INITIAL_CAP]; 
    int arrCnt= 0; 
    while (infile.hasNextInt()) 
    { 
     if (arrCnt==arr.length) 
      arr = doubleMyLength(arr); 
     insertInOrder(arr, arrCnt, infile.nextInt()); 
     ++arrCnt; 
    } 
    infile.close(); 

    arr = trimMyLength(arr, arrCnt); 
    System.out.println("Sorted array of " + arr.length + " ints from " + args[0] + " after insert in order:"); 
    printArray(arr); // we trimmed it so count == length so we don't bother to pass in count

來源

2014-03-01 user3287300

你只能做一個已排序數組的二進制搜索。 – halex

請顯示一些如何調用'insertInOrder（i []，i，i）'的例子。 – aliteralmind

我正在逐一讀取數字，但我想使用二進制搜索來查找下一個傳入數字的插入索引 – user3287300

當newVal沒有在數組中（這是很可能發生的），你bSearch()回報-1 。然後，insertInOrder()始終將該項目插入到位置index = -1 - index，即0。這就是爲什麼結果是錯誤的。

爲了正確，bSearch()需要返回值大於newVal的最小索引。

來源

2014-03-01 02:24:08 timrau

這項工作？ if（lo> hi） return - （lo + 1）; – user3287300

@ user3287300那麼你的測試結果是什麼？ – timrau

你的代碼有兩個問題。正如@timrau所指出的那樣，如果找不到條目，則從二分查找方法返回錯誤的值-1。您應該返回-lo - 1。（這是你應該插入值的地方 - 返回一個負值用於表示在二進制搜索中沒有找到該值，但在你的情況下，你不關心在排序列表中獲取重複值，所以您可以直接返回lo）。

其次，您將錯誤的數組長度傳遞給您的二分查找方法。它應該是cnt - 1而不是arr.length - 1。

代碼變爲：

static void insertInOrder(int[] arr, int cnt, int newVal) { 
    int index = bSearch(arr, 0, cnt - 1, newVal); 
    if (index < 0) { 
     index = -1 - index; 
    } 
    for (int i = cnt; i >= index + 1; --i) { 
     arr[i] = arr[i - 1]; 
    } 

    arr[index] = newVal; 
} 

public static int bSearch(int[] a, int lo, int hi, int key) { 
    int mid = (lo + hi)/2; 
    if (lo > hi) 
     return -lo - 1; 
    else if (a[mid] == key) 
     return mid; 
    else if (a[mid] < key) 
     return bSearch(a, mid + 1, hi, key); 
    else 
     return bSearch(a, lo, mid - 1, key); 
}

來源

2014-03-01 02:39:32

二進制搜索和插入排序

回答

相關問題