java - if-else 语句内的递归调用

Question

我不明白为什么我的程序在包含在条件语句中时会递归地调用自身。我正在做一个演示快速选择的作业，这是快速排序的一种变体，可以让你找到第 k 个最小的元素。我不想太冗长，所以我发布了问题代码，希望我的解释能让您了解我的目标。

在下面的代码块中，k 是我要查找的第 k 个元素。 l 是下边界，其左侧的所有数字都小于主元。这个想法是如果 k 落在下边界和 l 之间，则搜索这一边。

    if (k-1<l) {
        System.out.println("call quickSelect from " + begin + " to " + l);
        if (l-1==begin) 
            {return begin;} //added to prevent random from throwing error
        else {                  
            depth++;
            return quickSelect(arr,k,begin,l-1);            }
    }

当我在 l-1==begin 时递归调用 quickSelect 时，问题就出现了。我在线程“main”java.lang.IllegalArgumentException 中收到错误 Exception:绑定(bind)必须为正 因为我使用的是 Java 的随机对象(我用它来查找边界内的主元)只能取正整数。因此，这就是为什么我添加了条件语句 l-1==begin 来防止在无效参数内调用 QuickSelect()。但是，我得到了同样的错误!我对这种情况的发生感到惊讶，因为我认为 if-else 语句可以处理这个异常。我真的很感激任何有关如何使用 l-1==begin 调用 fastSelect 的想法。我已经包含了下面程序的完整代码以获取更多详细信息，递归调用位于底部。

import java.util.Scanner;
import java.io.FileNotFoundException;
import java.io.File;
import java.util.ArrayList;
import java.util.Random;
import java.util.Collections;

public class quickSelect{ 
    static int depth=0;
    public static void main(String args[]) {
        int totalDepth=0;
        ArrayList<Integer>al = new ArrayList();             
        Scanner doc = new Scanner("");
//      String smallFile = "proj2small.txt";
        String smallFile = "proj2big.txt";

        try {
            File openSmallFile=new File(smallFile);
            doc = new Scanner(openSmallFile);
        } catch (FileNotFoundException e1 ) {
            e1.printStackTrace();
        }
        while (doc.hasNext()) {
            int f = doc.nextInt();
            al.add(f);
        }
        int k=al.size()/2;
            depth=0;
            int p = quickSelect(al,k,0,al.size()-1);
            System.out.println(k + "th element is " + p);
            System.out.println(depth + " recursive calls ");
        }       

    public static int quickSelect(ArrayList<Integer>arr,int k,int begin,int end) {
        Random rand = new Random();
        int range = end-begin;
        int j = rand.nextInt(range);
        //int equals=0;
        int pivot = arr.get(j+begin);
        System.out.println("pivot is " + pivot + " at index " + (j+begin));
        int h=end-1;
        int l=begin;
        arr.remove(j+begin);//remove the pivot. Assume no duplicates are allowed
        if (j+begin<k) {
            k--; //shift k left one if index of pivot comes before it because we removed pivot
        }
        while (true) {
            while (arr.get(l)<pivot) {
                l++;
            }
            while(arr.get(h)>pivot) {
                h--;
            }
            if(l>=h) {
                break;
            }
            Collections.swap(arr, l, h);
            l++;
            h--;

        }
        //l is equal to the pivot? 
        //System.out.println("l is " + ((arr.get(l)==pivot)?"equal":"not equal") + " to the pivot");
        System.out.println("k is " + k);

        if (k-1<l) { //l-1 because left shift one after removal
            System.out.println("call quickSelect from " + begin + " to " + l);
            if (l-1==begin) 
            {return begin;} //added to prevent random from throwing error
            else {                  
                            depth++;
                return quickSelect(arr,k,begin,l-1); //array gets smaller k becomes smaller
            }
        }
        else if (k-1==l) {
            return pivot;
        }
        else {
            System.out.println("call quickSelect from " + l + " to " + end);
            if (end-1==l) 
            {return l;} //added to prevent random from throwing error
            else {
                return quickSelect(arr,k,l,end-1); //we removed the pivot so l is part of the high range
            }
        }   
    }
}

ps 对有趣的代码格式表示抱歉。从 Eclipse 粘贴不是一个好主意

Answer 1

如果您的文件包含零个或仅一个值，则 al.size() 的值将为 0 或 1。

因此，无论哪种方式，k 都将为 0，因为 0/2 和 1/2 都等于 0。

因此，当您将 al.size()-1 作为该方法的 end 传递时，在 quickSelect() 的第一次运行中，它传递 0-1，当然是 -1。

当您调用 nextInt(0, -1) 时，会抛出 IllegalArgumentException 并给出错误。