Dart实现二分查找返回-1的问题排查与解决

我用Dart实现二分查找（之前在Python里已经跑通了），测试第一个边缘用例时，locate_card函数总是返回错误的-1，但把函数里的return -1;注释掉后，就能得到正确结果。相关代码如下：

main.dart #

import 'edgecases.dart';
main () {
  var card = edgecases(0)['input']['cards'];
  var query = edgecases(0)['input']['query'];
  var result = locate_card(edgecases(0)['input']['cards'], edgecases(0)['input']['query']);
  var output = edgecases(0)['output'];
  print("Cards:- $card");
  print("Query:- $query");
  print("Output:- $result");
  print("Actual answer:- $output");
}

edgecases.dart #

edgecases ([edgecasenumber = null]) { //You may make it required, I provided a null as default to check if my syntax is going right.
  List tests = [];                    
  var edge1 = {'input': {
        'cards': [13, 11, 10, 7, 4, 3, 1, 0],
        'query': 1
    }, 'output': 6};
  tests.addAll([edge1]);
  if (edgecasenumber == null){  // This if is useless here so you may 
    return 'Null type object coud not be found.';
  } else {
     return tests.elementAt(edgecasenumber); // Indexing in dart also starts with 0.
  }
}

locate_card (List cards, int query){
  int lo = 0;
  int hi = cards.length - 1;
  print('$lo  $hi');
  while (lo <= hi) {
    //print('hello'); Uncomment to see if it is entering the loop
    var mid = (lo + hi) ~/ 2;
    var mid_number = cards[mid];

    print("lo:$lo ,hi:$hi, mid:$mid, mid_number:$mid_number");

    if (mid_number == query){
      return mid;
    } else if (mid_number < query) {
      hi = mid - 1;
    } else if (mid_number > query) {
      lo = mid + 1;
    };
  return -1; //taking about this line

  };
}

问题原因 #

核心问题是return -1;的位置错误：它被写在了while循环的内部。

执行流程是这样的：第一次进入循环，计算mid后，不管有没有找到目标值，执行完分支判断后，都会立刻执行return -1;，直接退出函数，根本没有机会继续循环查找正确的位置。比如测试用例里，第一次mid是3，mid_number是7，比query（1）大，于是设置lo=4，之后马上执行return -1，函数直接返回-1，自然得不到正确结果。

注释掉return -1;后，循环会继续执行，直到找到目标值时触发return mid;返回正确索引，所以能得到正确结果。不过这种情况如果没找到目标，函数会返回null，逻辑还是不完整。

解决方法 #

把return -1;移到while循环的外面，确保只有当整个循环结束（也就是lo > hi，确认目标不存在）时，才返回-1：

修改后的locate_card函数：

locate_card (List cards, int query){
  int lo = 0;
  int hi = cards.length - 1;
  print('$lo  $hi');
  while (lo <= hi) {
    var mid = (lo + hi) ~/ 2;
    var mid_number = cards[mid];

    print("lo:$lo ,hi:$hi, mid:$mid, mid_number:$mid_number");

    if (mid_number == query){
      return mid;
    } else if (mid_number < query) {
      hi = mid - 1;
    } else if (mid_number > query) {
      lo = mid + 1;
    };
  }
  return -1; // 移到循环外面
}

这样逻辑就完整了：循环过程中找到目标就返回对应索引，循环结束没找到就返回-1。

内容的提问来源于stack exchange，提问作者Bhaumik Tripathi