summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-10-05 22:14:28 -0500
committerHaidong Ji2018-10-05 22:14:28 -0500
commitb75fb4d4a4503dac26efa4380eb38f89c010bb19 (patch)
treece069452c856e122a8416042d2bdc52eb2f13906
parent948cfbc5364931ec98112d89690472a6d457fcdb (diff)
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.
-rw-r--r--AlgoDesignAndTechniqueEdxJava/sources/BinarySearch.java29
1 files 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 {