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(-)

(limited to 'AlgoDesignAndTechniqueEdxJava')

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