二进制搜索和插入排序

我的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

二进制搜索和插入排序

回答

相关问题