8

我一直在利用我的大学时间通过编码算法练习 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;
            }
        }
    }
}

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

4

8 回答 8

30

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

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);
    }
}
于 2013-09-25T18:52:50.900 回答
7

这是一种更简单的二分查找方法：

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
}
于 2013-09-25T18:52:44.697 回答
2

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

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;
        }
    }
}

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

1. shouldReturnFalseIfArrayIsEmpty()
2. shouldReturnFalseIfNotFoundInSortedOddArray()
3. shouldReturnFalseIfNotFoundInSortedEvenArray()
4. shouldReturnTrueIfFoundAsFirstInSortedArray()
5. shouldReturnTrueIfFoundAtEndInSortedArray()
6. shouldReturnTrueIfFoundInMiddleInSortedArray()
7. shouldReturnTrueIfFoundAnywhereInSortedArray()
8. shouldReturnFalseIfNotFoundInSortedArray()
于 2013-11-03T09:16:25.323 回答
2

一个可能的例子是：

// 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);
   }

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

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

于 2017-05-08T11:57:35.560 回答
1

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

public boolean binarysearchRecursion(Array, begin_index,end_index, search_element)
  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. If mid_element<search_element用 for range 调用你的方法mid+1 - Length_of_Array

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

于 2013-09-25T18:53:15.723 回答
1

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

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;
            }
        }
    }
}
于 2015-12-31T11:22:21.463 回答
0

虽然它不返回索引，但这至少返回了集合中有东西的“是”或“否”的想法：

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;
}
于 2016-12-14T00:19:44.817 回答
0

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

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

实施

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;
    }
}
于 2017-03-27T12:40:04.897 回答