Java 如何使用递归创建二分搜索算法

How to use recursion in creating a binary search algorithm

提问by JP24

I have been using my time off university to practice Java through coding algorithms. One of the algorithms I coded was the binary search:

我一直在利用大学期间的时间通过编码算法练习 Java。我编码的算法之一是二进制搜索：

public class BinarySearch {

    private static int list[] = {3, 6, 7, 8, 9, 10};

    public static void main(String[] args) {
        BinarySearch b = new BinarySearch();
        b.binarySearch(list);

    }

    public void binarySearch(int[] args) {
        System.out.println("Binary search.");

        int upperBound = args.length;
        int lowerBound = 1;
        int midpoint = (upperBound + lowerBound) / 2;
        int difference = upperBound - lowerBound;

        int search = 7;

        for (int i = 0; i < args.length; i++) {
            if (search < args[midpoint - 1] && difference != 1) {
                upperBound = midpoint - 1;
                midpoint = upperBound / 2;
            } else if (search > args[midpoint - 1] && difference != 1) {
                lowerBound = midpoint + 1;
                midpoint = (lowerBound + upperBound) / 2;

            } else if (search == args[midpoint - 1]) {
                midpoint = midpoint - 1;

                System.out.println("We found " + search + " at position " + midpoint + " in the list.");
                i = args.length;
            } else {
                System.out.println("We couldn't find " + search + " in the list.");
                i = args.length;
            }
        }
    }
}

I really want to be able to write a much cleaner and efficient binary search algorithm, an alternative to what I've coded. I have seen examples of how recursion is used such as when doing factorial with numbers which I understand. However when coding something of this complexity I am confused on how to use it to my advantage. Therefore my question is how do I apply recursion when coding a binary search algorithm. And if you have any tips for me to perfect my recursion skills even if it has to be something that doesn't regard to binary search then please feel free to post.

我真的希望能够编写一个更干净、更高效的二进制搜索算法，作为我编码的替代方案。我已经看到了如何使用递归的示例，例如在对我理解的数字进行阶乘时。然而，当编码这种复杂的东西时，我对如何利用它来发挥我的优势感到困惑。因此，我的问题是在编码二进制搜索算法时如何应用递归。如果您对我完善我的递归技能有任何提示，即使它必须与二分搜索无关，那么请随时发布。

采纳答案by Cruncher

If you really want to use recursion, this should do it.

如果你真的想使用递归，这应该这样做。

public static int binarySearch(int[] a, int target) {
    return binarySearch(a, 0, a.length-1, target);
}

public static int binarySearch(int[] a, int start, int end, int target) {
    int middle = (start + end) / 2;
    if(end < start) {
        return -1;
    } 

    if(target==a[middle]) {
        return middle;
    } else if(target<a[middle]) {
        return binarySearch(a, start, middle - 1, target);
    } else {
        return binarySearch(a, middle + 1, end, target);
    }
}

回答by Sajal Dutta

Here is an easier way of doing binary search:

这是进行二分搜索的更简单方法：

public static int binarySearch(int intToSearch, int[] sortedArray) {

    int lower = 0;
    int upper = sortedArray.length - 1;

    while (lower <= upper) {

        int mid = lower + (upper - lower) / 2;

        if(intToSearch < sortedArray[mid]) 

            upper = mid - 1;

        else if (intToSearch > sortedArray[mid]) 

            lower = mid + 1;

        else 

            return mid;
    }

    return -1; // Returns -1 if no match is found
}

回答by Prateek

Here is a algorithm which should get you going. Let your method signature be:

这是一个应该让你前进的算法。让你的方法签名是：

public boolean binarysearchRecursion(Array, begin_index,end_index, search_element)

1. Check if your begin_index > end_index if YES then return false.
2. Calculate mid_elementfor your input array.
3. Check if your search_elementis equal to this mid_element. if YES return true
4. If mid_element> search_elementCall your method with for range 0 - mid
5. If mid_element< search_elementCall your method with for range mid+1 - Length_of_Array

1. 检查您的 begin_index > end_index 如果是，则返回false。
2. 计算mid_element您的输入数组。
3. 检查您的search_element是否等于 this mid_element。如果是返回true
4. 如果mid_element>search_element使用 for 调用您的方法range 0 - mid
5. 如果mid_element<search_element使用 for 范围调用您的方法mid+1 - Length_of_Array

Also as @DwB said in his comment you are better using loop to get things done. Some problems are recursive in nature(Like binary tree problems). But this one is not one of them.

同样正如@DwB 在他的评论中所说，你最好使用循环来完成工作。有些问题本质上是递归的（比如二叉树问题）。但这一个不是其中之一。

回答by lkamal

Following is a code sample extracted from here.

以下是从此处提取的代码示例。

public class BinarySearch {

    public boolean find(int[] sortedValues, int value) {
        return search(sortedValues, value, 0, sortedValues.length - 1);
    }

    private boolean search(int[] sorted, int value, int leftIndex, int rightIndex) {

        // 1. index check
        if (leftIndex > rightIndex) {
            return false;
        }

        // 2. middle index
        int middle = (rightIndex + leftIndex) / 2;

        // 3. recursive invoke
        if (sorted[middle] > value) {
            return search(sorted, value, leftIndex, middle - 1);
        } else if (sorted[middle] < value) {
            return search(sorted, value, middle + 1, rightIndex);
        } else {
            return true;
        }
    }
}

You can find implementations of the below test cases against the above binary search implementation as well in the reference link.

您还可以在参考链接中找到针对上述二进制搜索实现的以下测试用例的实现。

1. shouldReturnFalseIfArrayIsEmpty()
2. shouldReturnFalseIfNotFoundInSortedOddArray()
3. shouldReturnFalseIfNotFoundInSortedEvenArray()
4. shouldReturnTrueIfFoundAsFirstInSortedArray()
5. shouldReturnTrueIfFoundAtEndInSortedArray()
6. shouldReturnTrueIfFoundInMiddleInSortedArray()
7. shouldReturnTrueIfFoundAnywhereInSortedArray()
8. shouldReturnFalseIfNotFoundInSortedArray()

回答by Michele Orsi

This is another way of doing recursion:

这是进行递归的另一种方式：

int[] n = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
@Test
public void testRecursiveSolution() {
    Assert.assertEquals(0, recursiveBinarySearch(1,n));
    Assert.assertEquals(15, recursiveBinarySearch(16,n));
    Assert.assertEquals(14, recursiveBinarySearch(15,n));
    Assert.assertEquals(13, recursiveBinarySearch(14,n));
    Assert.assertEquals(12, recursiveBinarySearch(13,n));
    Assert.assertEquals(11, recursiveBinarySearch(12,n));
    Assert.assertEquals(10, recursiveBinarySearch(11,n));
    Assert.assertEquals(9, recursiveBinarySearch(10,n));
    Assert.assertEquals(-1, recursiveBinarySearch(100,n));
}
private int recursiveBinarySearch(int n, int[] array) {
    if(array.length==1) {
        if(array[0]==n) {
            return 0;
        } else {
            return -1;
        }
    } else {
        int mid = (array.length-1)/2;
        if(array[mid]==n) {
            return mid;
        } else if(array[mid]>n) {
            return recursiveBinarySearch(n, Arrays.copyOfRange(array, 0, mid));
        } else {
            int returnIndex = recursiveBinarySearch(n, Arrays.copyOfRange(array, mid+1, array.length));
            if(returnIndex>=0) {
                return returnIndex+mid+1;
            } else {
                return returnIndex;
            }
        }
    }
}

回答by Lorena Nicole

While it doesn't return the index, this at least returns the idea of 'yes' or 'no' that something is in the collection:

虽然它不返回索引，但这至少会返回集合中存在“是”或“否”的想法：

public static boolean recursive(int[] input, int valueToFind) {
    if (input.length == 0) {
        return false;
    }

    int mid = input.length / 2;
    if (input[mid] == valueToFind) {
        return true;
    } else if (input[mid] > valueToFind) {
        int[] smallerInput = Arrays.copyOfRange(input, 0, mid);
        return recursive(smallerInput, valueToFind);
    } else if (input[mid] < valueToFind) {
        int[] smallerInput = Arrays.copyOfRange(input, mid+1, input.length);
        return recursive(smallerInput, valueToFind);
    }

    return false;
}

回答by Daniel Ferreira Castro

A recursion BinarySearch with break conditions in case you can not find the value you are looking for

带有中断条件的递归 BinarySearch，以防您找不到要查找的值

public interface Searcher{
    public int search(int [] data, int target, int low, int high);
}

The Implementation

实施

public class BinarySearch implements Searcher {

    public int search(int[] data, int target, int low, int high) {
        //The return variable
        int retorno = -1;
        if(low > high) return retorno;
        int middle = (high + low)/2;
        if(target == data[middle]){
            retorno = data[middle];
        }else if(target < data[middle] && (middle - 1 != high)){
            //the (middle - 1 != high) avoids beeing locked inside a never ending recursion loop
            retorno = search(data, target, low, middle - 1);
        }else if(target > data[middle] && (middle - 1 != low)){
            //the (middle - 1 != low) avoids beeing locked inside a never ending recursion loop
            retorno = search(data, target, middle - 1, high);
        }else if(middle - 1 == low || middle - 1 == high){
            //Break condition if you can not find the desired balue
            retorno =  -1;
        }
        return retorno;
    }
}

回答by delive

A possible example is :

一个可能的例子是：

// need extra "helper" method, feed in params
   public int binarySearch(int[] a, int x) { 
      return binarySearch(a, x, 0, a.length - 1);
   }

   // need extra low and high parameters
   private int binarySearch(int[ ] a, int x,
         int low, int high) {
      if (low > high) return -1; 
      int mid = (low + high)/2;
      if (a[mid] == x) return mid;
      else if (a[mid] < x)
         return binarySearch(a, x, mid+1, high);
      else // last possibility: a[mid] > x
         return binarySearch(a, x, low, mid-1);
   }

Here you can check in C Binary Search, With and Without Recursion

在这里你可以检查 C 二进制搜索，有和没有递归

Source : http://www.cs.utsa.edu/~wagner/CS3343/recursion/binsearch.html

来源：http: //www.cs.utsa.edu/~wagner/CS3343/recursion/binsearch.html