0

我已经编写了一个简单的方法来将新元素添加到排序列表类中，代码在 Dart 中，但在所有类似 C 的语言中发生的事情应该相当明显，我已经对其运行了几个简单的单元测试，它似乎确实以正确的顺序添加了新元素，我的问题是，它是否充分证明？它可以更有效吗？我正在尝试使用二进制搜索来找到要插入的适当索引，它还返回插入新对象的索引：

int add(T obj){

  int loIdx = 0;
  int upIdx = list.length - 1;
  int i;

  while(loIdx <= upIdx){

    i = loIdx + ((upIdx - loIdx) >> 1);

    switch(_compare(obj, list[i])){

      case 0:

        loIdx = i;

        upIdx = i - 1;

        break;

      case -1:

        upIdx = i - 1;

        if(loIdx == upIdx){

          if(_compare(obj, list[loIdx]) == 1){

            loIdx++;

          }

        }

        break;

      case 1:

        loIdx = i + 1;

        break;

    }

  }

  list.insert(loIdx, obj);

  return loIdx;

}

为了完整起见，这是我用来证明它确实有效的单元测试之一：

test('Order',(){

  SortedList<int> intList = new SortedList<int>((int a, int b) => a.compareTo(b));

  intList.add(5);
  intList.add(7);
  intList.add(0);
  intList.add(3);
  intList.add(6);
  intList.add(9);
  intList.add(1);
  intList.add(2);
  intList.add(8);
  intList.add(5);
  intList.add(4);

  expect(intList.list, orderedEquals([0,1,2,3,4,5,5,6,7,8,9]));

});
4

1 回答 1

2

我从来没有使用过 Dart，但是这条线：

i = loIdx + ((upIdx - loIdx) % 2);

看起来真的很奇怪。通常我希望看到类似的东西：

i = loIdx + ((upIdx - loIdx) >> 1);

或者

i = loIdx + ((upIdx - loIdx) / 2);
于 2013-10-27T22:32:49.213 回答