Add files via upload

SagarKumar04 · web-flow · commit 63a2a869bf42 · 2021-08-02T23:09:09.000+05:30
diff --git a/DivideAndConquer/MedianOfTwoSortedArrays.java b/DivideAndConquer/MedianOfTwoSortedArrays.java
@@ -0,0 +1,44 @@
+package InfinityJune21.DivideAndConquer;
+
+public class MedianOfTwoSortedArrays {
+    static int getMedian(int arr1[], int arr2[], int n) {
+        int i = 0, j = 0, count, m1 = -1, m2 = -1;
+
+        for(count = 0; count <= n; count++) {
+            if(arr1[i] <= arr2[j]) {
+                m1 = m2;
+                m2 = arr1[i];
+                i++;
+            }
+            else {
+                m1 = m2;
+                m2 = arr2[j];
+                j++;
+            }
+        }
+
+        int median = (m1 + m2) / 2;
+
+        return median;
+    }
+
+    public static void main(String[] args) {
+        int arr1[] = {1, 13, 25, 40, 50};
+        int arr2[] = {2, 17, 30, 45, 70};
+        /*
+        Merged array: 1, 2, 13, 17, 25, 30, 40, 45, 50, 70
+        (25 + 30) / 2 = 27
+         */
+
+        int n1 = arr1.length;
+        int n2 = arr2.length;
+
+        if(n1 == n2) {
+            int median = getMedian(arr1, arr2, n1);
+            System.out.println(median);
+        }
+        else {
+            System.out.println("Size of arrays are not equal");
+        }
+    }
+}
diff --git a/DivideAndConquer/OptimisedPowerCalculation.java b/DivideAndConquer/OptimisedPowerCalculation.java
@@ -0,0 +1,26 @@
+package InfinityJune21.DivideAndConquer;
+
+public class OptimisedPowerCalculation {
+    static int power(int x, int y) {
+        if(y == 0) {
+            return 1;
+        }
+
+        int temp = power(x, y / 2);
+        if(y % 2 == 0) {
+            return (temp * temp);
+        }
+        else {
+            return (x * temp * temp);
+        }
+    }
+
+    public static void main(String[] args) {
+        int x = 8;
+        int y = 3;
+
+        int xPowerY = power(x, y);
+
+        System.out.println(xPowerY);
+    }
+}
diff --git a/DivideAndConquer/PowerCalculation.java b/DivideAndConquer/PowerCalculation.java
@@ -0,0 +1,24 @@
+package InfinityJune21.DivideAndConquer;
+
+public class PowerCalculation {
+    static int power(int x, int y) {
+        if(y == 0) {
+            return 1;
+        }
+        else if(y % 2 == 0) {
+            return (power(x, y / 2) * power(x, y / 2));
+        }
+        else {
+            return (x * power(x, y / 2) * power(x, y / 2));
+        }
+    }
+
+    public static void main(String[] args) {
+        int x = 8;
+        int y = 3;
+
+        int xPowerY = power(x, y);
+
+        System.out.println(xPowerY);
+    }
+}
diff --git a/DivideAndConquer/PowerCalculationOfNegativePowers.java b/DivideAndConquer/PowerCalculationOfNegativePowers.java
@@ -0,0 +1,31 @@
+package InfinityJune21.DivideAndConquer;
+
+public class PowerCalculationOfNegativePowers {
+    static float power(int x, int y) {
+        if(y == 0) {
+            return 1;
+        }
+
+        float temp = power(x, y / 2);
+        if(y % 2 == 0) {
+            return (temp * temp);
+        }
+        else {
+            if(y > 0) {
+                return (x * temp * temp);
+            }
+            else {
+                return (temp * temp / x);
+            }
+        }
+    }
+
+    public static void main(String[] args) {
+        int x = 8;
+        int y = -5;
+
+        float xPowerY = power(x, y);
+
+        System.out.println(xPowerY);
+    }
+}
diff --git a/SearchTechniques/InterpolationSearch.java b/SearchTechniques/InterpolationSearch.java
@@ -1,7 +1,34 @@
 package InfinityJune21.SearchTechniques;
 
 public class InterpolationSearch {
+    static int interpolationSearch(int arr[], int lo, int hi, int element) {
+        int pos;
+
+        if(lo <= hi && element >= arr[lo] && element <= arr[hi]) {
+            pos = lo + ((hi - lo) / (arr[hi] - arr[lo])) * (element - arr[lo]);
+
+            if(arr[pos] == element) {
+                return pos;
+            }
+
+            if(arr[pos] < element) {
+                return interpolationSearch(arr, pos + 1, hi, element);
+            }
+
+            if(arr[pos] > element) {
+                return interpolationSearch(arr, lo, pos - 1, element);
+            }
+        }
+
+        return -1;
+    }
+
     public static void main(String[] args) {
+        int arr[] = {10, 12, 20, 24, 25, 35, 42, 50, 61, 73};
+        int length = arr.length;
+        int element = 61;
+        int index = interpolationSearch(arr, 0, length - 1, element);
 
+        System.out.println("Index: " + index);
     }
 }
