区间表示不同导致二分查找程序的差异

给定一个有序序列（下面成为数组），二分查找通过一步步缩小有序序列的区间，最终查找要查找元素所在的下标，或未查找到该元素。而区间的基本表示法有三种：

• 使用数组的两个下标表示，其中一个下标表示区间开始，另外一个下标表示区间结束, First, Last；
• 直接使用一个子数组表示区间；
• 使用数组的一个下标表示区间起始，另外区间长度来表示区间, Index, Length。
  

下面为使用这三种表示法所写的程序：

方法一：

%% 二分查找程序

%% 输入: Value 要查找的值

%%       Array 有序数组

%% 输出: -1 未查找到该值 或 索引

chop(_Value, []) ->

    -1;

chop(Value, Array) ->

    chop_help(Value, Array, 1, length(Array)).

chop_help(_Value, _Array, First, Last) when First > Last ->

    -1;

chop_help(Value, Array, First, Last) ->

    Mid = (First + Last) div 2,

    MidValue = lists:nth(Mid, Array),

    if 

        Value == MidValue -> Mid;

        Value < MidValue -> chop_help(Value, Array, First, Mid-1);

        true -> chop_help(Value, Array, Mid+1, Last)

    end.

方法二：

chop(_Value, []) ->

    -1;

chop(Value, Array) ->

    Mid = (1 + length(Array)) div 2,

    MidValue = lists:nth(Mid, Array),

    if

        Value == MidValue -> Mid;

        Value < MidValue -> 

            LeftList = lists:sublist(Array, Mid-1),

            NowIndex = chop(Value, LeftList),

            compute_index(NowIndex, 0);

        true -> % Value > MidValue

            RightList = lists:sublist(Array, Mid+1, length(Array) - Mid),

            NowIndex = chop(Value, RightList),

            compute_index(NowIndex, Mid)

    end.

compute_index(NowIndex, BaseIndex) ->

     case NowIndex of

         -1 -> -1;

         _ -> NowIndex + BaseIndex

     end.

方法三：

chop(Value, Array) ->

    chop_help(Value, Array, 1, length(Array)).

chop_help(_Value, _Array, _Index, Length) when Length =< 0 ->

    -1;

chop_help(Value, Array, Index, Length) ->

    Mid = Index + Length div 2,

    MidValue = lists:nth(Mid, Array),

    if 

        Value == MidValue -> Mid;

        Value < MidValue ->

            chop_help(Value, Array, Index, Mid - Index);

        true ->

            chop_help(Value, Array, Mid + 1, Length - (Mid - Index) - 1)

    end.

这三个程序本身并不复杂，相反编写的过程反而更有趣：

1. 这三个程序是分三天写的，第一天写了第一个，而且很快，没出现什么错误；第二天写的是用第二种方法写的，原因是渐渐感觉到如果不传递上下标，而把数组切片传进去，也行；在使用第二中方法编写完后，突然觉得这是因为用来表示区间的方法不同，导致程序的不同，因此想到了第三种方法；
2. 在这三个程序的实现过程中，第三个程序实现最快，第二个最慢，第一种方法尽管要写测试代码，但还是比第二种方法快，而且第二种方法出现的错误也最多；
3. 第一种方法是在学校里就写过的，而且使用两个下标来表示区间非常简单；第二种方法每次递归时都传递进去一个子数组，其起始地址都是0，因此需在每次递归时都返回基础下标，最终把它们加起来得到最后元素的坐标。