From b75fb4d4a4503dac26efa4380eb38f89c010bb19 Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Fri, 5 Oct 2018 22:14:28 -0500 Subject: Binary search recursive approach The grader showed that it took less time, but more space. There might be some sampling issues, since I ran both approach only once.--- .../sources/BinarySearch.java | 29 +++++++++------------- 1 file changed, 12 insertions(+), 17 deletions(-) diff --git a/AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java b/AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java index 9eb5915..32fcb04 100644 --- a/AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java +++ b/AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java @@ -26,24 +26,19 @@ public class BinarySearch { } public static int binarySearch(int[] a, int key) { - int low = 0; - int high = a.length - 1; - int mid = 0; - boolean found = false; - while (low <= high) { - mid = (int) Math.floor(low + (high - low) / 2); - if (key == a[mid]) { - found = true; - return mid; - } else if (key < a[mid]) - high = mid - 1; - else - low = mid + 1; - } - if (found) - return low - 1; - else + return binarySearchRecursive(a, 0, a.length - 1, key); + } + + public static int binarySearchRecursive(int[] a, int low, int high, int key) { + if (high < low) return -1; + int mid = (int) Math.floor(low + (high - low) / 2); + if (key == a[mid]) { + return mid; + } else if (key < a[mid]) + return binarySearchRecursive(a, low, mid - 1, key); + else + return binarySearchRecursive(a, mid + 1, high, key); } static class FastScanner { -- cgit v1.2.3