2个函数合并

BuTa丶潇

大家好，我在用perl实现：有a和b，在一个有序数组中查询，a为第一个可以插入的位置，b为最后一个可以插入的位置。
举例：数组：2，4，7，8   而a=3，b=8  那么a的位置a_pos即为1, b的位置b_pos为3。
                                 或者a=3，b=6，那么为--------------1,-----------------1。

我用了2个函数来进行这个实现：
$right=@array-1;
$a_pos = &chaxun_a(0,$right);
$b_pos=&charxun_b(0,$right);

sub chaxun_a{
        my ($left, $right) = @_;
        my $mid = int(($left+$right)/2);
        if( $a <= $array[$mid] ) {
                return $mid if ( $a >= $array[$mid-1] );
                chaxun_a( $left,$mid  );
        } else {
                chaxun_a( $mid, $right);
        }
}

sub chaxun_b{
        my ($left, $right) = @_;
        my $mid = int(($left+$right)/2);
        if( $b > $array[$mid] ) {
                return $mid if ( $b <= $array[$mid+1] );
                chaxun_b ( $mid , $right );
        } else {
                chaxun_b ( $left , $mid  );
        }
}

现在感觉代码重复 因为chaxun_a和chaxun_b这2个函数 基本逻辑都差不多,里面就只是一小部分不相同, 所以想进行下合并,为一个函数。
我想到的思路是chaxun(0,$right,'a'),就是给函数加一个标志,如果是‘a’ 那么就以chaxun_a的方式进行,如果传入'b',同理。

但是现在遇到的问题是，我合并不起来。。合并完发现代码比之前的还要冗余和麻烦。{:3_194:}

请问哪位朋友有好的思路帮我合并下吗..十分感谢！！

picbhan

你这不是在写二分法吗？

BuTa丶潇

回复 2# picbhan


    嗯是呀 但是我想把2个合并为一个 暂时想不到好的方法..能不能帮忙合并一下..{:3_193:}

Perlvim

真的看不懂
插入的原则是什么？
查询什么？
a=3,b=6 时为什么是 1 ... 1

BuTa丶潇

回复 4# Perlvim


    数组下标。{:3_193:}
你可以把a和b看作是一个区间 即[a,b]
那么查询所有数组中的元素在[a,b]区间中 匹配的元素下标。

如a=3 b=6 那么只有下标为1的适合,所以a能插入的位置即为1之前, b为1之后 所以a_pos和b_pos都是1
我描述的不是太清楚，不好意思。。

jason680

回复 1# BuTa丶潇

How about this

use strict;
use warnings;

my @aData = (2, 4, 7, 8);

my $a_pos = &chaxun(\@aData, "a", 3);
my $b_pos = &chaxun(\@aData, "b", 6);
print "a pos=$a_pos, b pos=$b_pos\n";

$a_pos = &chaxun(\@aData, "a", 3);
$b_pos = &chaxun(\@aData, "b", 8);
print "a pos=$a_pos, b pos=$b_pos\n";

sub chaxun{
  my ($raData, $sPoint, $sVal) = @_;
  my $sMax = scalar(@{$raData}) -1;
  my $sP = $sPoint eq "a" ? 1 : 0;

  my($sLeft, $sRight) = (0, $sMax);
  return 0 if($sVal <= $raData->[0]);
  return $sMax if($sVal >= $raData->[$sMax]);
  while(1){
    my $sMid = int(($sLeft + $sRight)/2);
    return $sMid if($sVal == $raData->[$sMid]);

    if( $sVal < $raData->[$sMid] ) {
      return $sMid-1+$sP if( $sVal > $raData->[$sMid-1]);
      $sRight = $sMid;
    }
    else{
      return $sMid+$sP   if( $sVal < $raData->[$sMid+1]);
      $sLeft = $sMid;
    }
  }
}

=== get result ====
a pos=1, b pos=1
a pos=1, b pos=3

   

BuTa丶潇

回复 6# jason680


    十分感谢! 就是我想要的合并程序，下面是我之前写的代码 感觉代码很长，重复的部分挺多。所以想合并下，可是合并后的代码更臃肿了。。{:3_194:}

   嗯，才接触perl不多，学到了很多知识，再次感谢！！

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. my $a=2;
   
6. my $b=3;
   
7. #my $b=3.5;
   
8. my @aData=("1","3","4"); #测试数据
   
9. my $sRight = @aData-1;
   
10. my ($a_pos,$b_pos);
    
11. &main;
    
12. 
    
13. sub main{
    
14.         if( $a <= $aData[0] ) {
    
15.                 $a_pos=0;
    
16.                 $b_pos= $b>=$aData[$sRight] ? $sRight : &charxun_b(0,$sRight);
    
17.         }
    
18.         elsif( $a >= $aData[$sRight] ) { #无
    
19.                 print "no fits!\n";
    
20.                 exit(0);
    
21.         }
    
22.         else {
    
23.                 $a_pos = &chaxun_a(0,$sRight);
    
24.                 $b_pos = $b<$aData[$sRight] ? &chaxun_b(0,$sRight) : $sRight;
    
25.         }
    
26.         print "a_pos=$a_pos,b_pos=$b_pos\n";
    
27. }
    
28. 
    
29. sub chaxun_a{
    
30.         my ($sLeft, $sRight) = @_;
    
31.         my $sMid = int(($sLeft+$sRight)/2);
    
32.         if( $a <= $aData[$sMid] ) {
    
33.                 return $sMid if ( $a >= $aData[$sMid-1] );
    
34.                 chaxun_a( $sLeft,$sMid  );
    
35.         } else {
    
36.                 chaxun_a( $sMid, $sRight);
    
37.         }
    
38. }
    
39. 
    
40. sub chaxun_b{
    
41.         my ($sLeft, $sRight) = @_;
    
42.         my $sMid = int(($sLeft+$sRight)/2);
    
43.         #print "sMid:$sMid\n";
    
44.         if( $b > $aData[$sMid] ) {
    
45.                 return $sMid if ( $b < $aData[$sMid+1] );
    
46.                 chaxun_b ( $sMid , $sRight );
    
47.         }
    
48.         elsif($b==$aData[$sMid]){
    
49.                 return $sMid if ($b<$aData[$sMid+1]);
    
50.                 chaxun_b($sMid,$sRight);
    
51.         }
    
52.         else {
    
53.                 chaxun_b ( $sLeft , $sMid  );
    
54.         }
    
55. }
    

复制代码

afukada

先確定一下我沒有搞錯你想要求的結果：

比方說array=( 2,4,7,8 )

所以你想找的是：

以( a,b )=( 3,6 )為例

                    | |2| |4| |7| |8| |
a可以在的位置       a
b可以在的位置            b

以( a,b )=( 3,8 )為例

                    | |2| |4| |7| |8| |
a可以在的位置       a
b可以在的位置            b    b    b

如果是這樣子

首先除了在array中有和a值相等的數字

否則a就只有一個位置

比方說array=( ...,3,3,3,... )<=array已經經過排序

那這裡如果a=3

有4個可以選擇的位置(就是4個逗號的地方)

所以我想到下面的想法：

先將a,b加入array進行排序

以( a,b )=( 3,6 ), array=( 2,4,7,8 )

a,b加入array排序後可得

( 2,3,4,6,7,8 )

將a,b範圍內的部分截取出來

( 3,4,6 )

element的個數扣除掉a及一個element=>即element個數-2為b可以在的位置<3-2=1>

然後將等於a的部分截取出來

( 3 )=>這裡的element個數為a可以在的位置<=1>

所以可以得到( pos_a,pos_b )=( 1,1 )

同理：

( a,b )=( 3,8 ), array=( 2,4,7,8 )

( 2,3,4,7,8,8 )

( 3,4,7,8,8 )=><5-2=3>

( 3 )=><=1>

所以可以得到( pos_a,pos_b )=( 1,3 )

下面是code

1. @array=(2,4,7,8);
   
2. 
   
3. ($pos_a,$pos_b)=chaxun(3,6,@array);
   
4. print "$pos_a,$pos_b\n";
   
5. ($pos_a,$pos_b)=chaxun(3,8,@array);
   
6. print "$pos_a,$pos_b\n";
   
7. 
   
8. sub chaxun($,$,@)
   
9. {
   
10.         my ($lower,$upper,@array)=@_;
    
11.         my @grep_array=grep{$_>=$lower&&$_<=$upper}sort{$a<=>$b}($lower,$upper,@array);
    
12.         return (scalar(grep{$_==$lower}@grep_array),scalar(@grep_array)-2);
    
13. }

复制代码

還有考慮a,b連在一起

比方說array=( 2,5,7,8 ),( a,b )=( 3,4 )

這樣子你要怎麼定義?

墨迹哥

不太能理解你的$a和$b怎么来的。。没有做声明。。。

BuTa丶潇

回复 8# afukada


    你好,这几天工作比较忙,所以上论坛的时间少了点,回复晚了不好意思。

   首先，你的问题是如果a和b连续怎么办，那么依然为“最小插入位置”和“最大插入位置”，

举例(a,b)=(4,5); (2,4,7,      #(2,4,7,的下标依次为0,1,2,3   
那么a的插入位置即为1,(即最小插入位置下标1之前),b的插入位置也为1(即最小插入位置下标1之后)

同样还有a b相等的情况：举例(a,b)=(4,4); (2,4,7,      #这里由于a b可以看作是一个范围,所以相等也是可能性条件之一
那么同样a的插入位置即为1,(即最小插入位置下标1之前),b的插入位置也为1(即最小插入位置下标1之后)

#------------------------

另外 谢谢你的代码哈 看的我好崇拜你{:3_193:} 。。我水平有限，一直写不出这样的代码 还再继续努力学习中。。


但是这里，我有个疑问，就是这样思路的情况下，那么如果数组很大的情况下 是否还适用呢。 夸张点举例，比如(2,4,7,8,23,...) 一个10W元素的有序数组。

当然我不是说这个程序，只是有这个疑惑。因为现实生活中，公司一般的数据毕竟不是常见的小型测试数据，很多很常用或者很漂亮的算法都不是特别适合。

还有就是 ： 就以我这个题目举例来看，我用了递归，还有的朋友用了递推。你用的是插入查找。
所以我就出现这个疑惑："处理大数据量的情况下,一般用什么思路或者方法比较能够兼容高效性呢?" 可以就这个题目为例帮我讲解下 谢谢哈。。{:3_193:}