khalid32 · March 26, 2020 10:18 · Mar 26, 2020 · Mar 26, 2020 · Mar 26, 2020 · Mar 26, 2020
diff --git a/Algorithm in Javascript b/Algorithm in Javascript
@@ -65,6 +65,47 @@ let binarySearch = (array, element, compare = defaultCompare) => {
 };
 
 
+// with Array View
+export let ArrayView = (
+    array,
+    start = 0,
+    end = array.length,
+) => ({
+    length: end - start,
+    toArray: () => array.slice(start, end),
+    slice: (dStart, dEnd) =>
+        ArrayView(array, start + dStart, start + dEnd),
+    get: (index) => {
+        let realIndex = start + index;
+        return realIndex < end && realIndex >= start
+            ? array[realIndex]
+            : undefined
+        ;
+    },
+});
+
+let binarySearchWithArrayView = (array, ...args) =>
+    binarySearchWithArraySplitting(ArrayView(array), ...args)
+
+let binarySearchWithArraySplitting = (array, element, compare = defaultCompare) => {
+    if (array.length === 0) { return -1; }
+    const middle = Math.floor(array.length / 2);
+    const comparison = compare(element, array.get(middle));
+
+    if (comparison === 0) { return middle; }
+
+    const [left, right] = comparison === -1
+        ? [0, middle - 1]
+        : [middle + 1, array.length];
+
+    const subIndex = binarySearchWithArraySplitting(array.slice(left, right), element, compare);
+
+    return subIndex === -1
+        ? -1
+        : left + subIndex;
+};
+
+
 binarySearch([], 2) // -1
 binarySearch([1], 1) // 0
 binarySearch([1], 2) // -1

diff --git a/Algorithm in Javascript b/Algorithm in Javascript
@@ -28,9 +28,9 @@ let binarySearch = (array, element, compare = defaultCompare, left = 0, right =
 
     return (
       comparison === -1 ?
-        binarySearchWithRecursion(array, element, compare, left, middle - 1)
+        binarySearch(array, element, compare, left, middle - 1)
     : comparison === 1 ?
-        binarySearchWithRecursion(array, element, compare, middle + 1, right)
+        binarySearch(array, element, compare, middle + 1, right)
     :
         middle
     );
@@ -48,7 +48,7 @@ let binarySearch = (array, element, compare = defaultCompare, left = 0, right =
         ? [left, middle - 1]
         : [middle + 1, right];
 
-    return binarySearchWithRecursion(array, element, compare, ...newBounds);
+    return binarySearch(array, element, compare, ...newBounds);
 };
 
 // Binary Search With Array Splitting
@@ -60,7 +60,7 @@ let binarySearch = (array, element, compare = defaultCompare) => {
     if (comparison === 0) { return middle; }
 
     const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length];
-    const subIndex = binarySearchWithArraySplitting(array.slice(left, right), element, compare);
+    const subIndex = binarySearch(array.slice(left, right), element, compare);
     return subIndex === -1 ? -1 : left + subIndex;
 };
 

diff --git a/Algorithm in Javascript b/Algorithm in Javascript
@@ -36,6 +36,33 @@ let binarySearch = (array, element, compare = defaultCompare, left = 0, right =
     );
 };
 
+// Binary Search With Tail Recursion
+let binarySearch = (array, element, compare = defaultCompare, left = 0, right = array.length - 1) => {
+    if (left > right) { return -1; }
+    const middle = Math.floor((right + left) / 2);
+    const comparison = compare(element, array[middle]);
+
+    if (comparison === 0) { return middle; }
+
+    const newBounds = comparison === -1
+        ? [left, middle - 1]
+        : [middle + 1, right];
+
+    return binarySearchWithRecursion(array, element, compare, ...newBounds);
+};
+
+// Binary Search With Array Splitting
+let binarySearch = (array, element, compare = defaultCompare) => {
+    if (array.length === 0) { return -1; }
+    const middle = Math.floor(array.length / 2);
+    const comparison = compare(element, array[middle]);
+
+    if (comparison === 0) { return middle; }
+
+    const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length];
+    const subIndex = binarySearchWithArraySplitting(array.slice(left, right), element, compare);
+    return subIndex === -1 ? -1 : left + subIndex;
+};
 
 
 binarySearch([], 2) // -1

diff --git a/Algorithm in Javascript b/Algorithm in Javascript
@@ -20,6 +20,24 @@ let binarySearch = (array, element, compare = defaultCompare) => {
     return -1;
 };
 
+// Binary Search With Recursion
+let binarySearch = (array, element, compare = defaultCompare, left = 0, right = array.length - 1) => {
+    if (left > right) { return -1; }
+    const middle = Math.floor((right + left) / 2);
+    const comparison = compare(element, array[middle]);
+
+    return (
+      comparison === -1 ?
+        binarySearchWithRecursion(array, element, compare, left, middle - 1)
+    : comparison === 1 ?
+        binarySearchWithRecursion(array, element, compare, middle + 1, right)
+    :
+        middle
+    );
+};
+
+
+
 binarySearch([], 2) // -1
 binarySearch([1], 1) // 0
 binarySearch([1], 2) // -1

diff --git a/Algorithm in Javascript b/Algorithm in Javascript
@@ -0,0 +1,29 @@
+/* Binary Search */
+
+/* Typical comparison function */
+let defaultCompare = (a, b) => a > b ? 1 : (a < b ? -1 : 0);
+
+// Binary Search With Loop
+let binarySearch = (array, element, compare = defaultCompare) => {
+    let left = 0;
+    let right = array.length - 1;
+
+    while (left <= right) {
+        let middle = Math.floor((right + left) / 2);
+
+        switch (compare(element, array[middle])) {
+            case -1: { right = middle - 1; break; }
+            case 1: { left = middle + 1; break; }
+            default: { return middle; }
+        }
+    }
+    return -1;
+};
+
+binarySearch([], 2) // -1
+binarySearch([1], 1) // 0
+binarySearch([1], 2) // -1
+binarySearch([1,2,3], 2) // 1
+binarySearch([1,2,3], 3) // 2
+binarySearch([1,2,3], 4) // -1
+binarySearch([1,2,3,7], 3) // 2
No results found