Merge branch 'master' into master

thuva4 · web-flow · commit f40ff20fb701 · 2017-10-25T09:54:59.000+05:30
diff --git a/BinarySearch/Javascript/binarySearch.js b/BinarySearch/Javascript/binarySearch.js
@@ -1,27 +1,31 @@
-/*Binary Search-Search a sorted array by repeatedly dividing the search interval
-* in half. Begin with an interval covering the whole array. If the value of the
-* search key is less than the item in the middle of the interval, narrow the interval
-* to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the
-* value is found or the interval is empty.
-*/
-
-function binarySearch(arr, i) {
-    var mid = Math.floor(arr.length / 2);
-    if (arr[mid] === i) {
-        console.log('match', arr[mid], i);
-        return arr[mid];
-    } else if (arr[mid] < i && arr.length > 1) {
-        binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
-    } else if (arr[mid] > i && arr.length > 1) {
-        binarySearch(arr.splice(0, mid), i);
-    } else {
-        console.log('not found', i);
-        return -1;
-    }
+/**
+ * Search a value into a sorted array by repeatedly dividing the search interval in half.
+ * @param  {Array}  arr Array to search into
+ * @param  {Number} k Value to search
+ * @return {Number} index of found item or -1 for not found
+ */
+function binarySearch(arr, k) {
+  let min = 0
+  let max = arr.length - 1
+  
+  while (min <= max) {
+    const cur = Math.floor((min + max) / 2)
+    if (arr[cur] === k) { return cur }
+    (arr[cur] > k)
+      ? max = cur - 1
+      : min = cur + 1
+  }
 
+  return -1
 }
 
-var ar=[1,2,3,4,5,6,7,8,9,10];
-binarySearch(ar,3);
-binarySearch(ar,7);
-binarySearch(ar,13);
+const arr = [1,2,3,4,5,6,7,8,9,10]
+console.log(binarySearch(arr, 6))  // 5
+console.log(binarySearch(arr, 9))  // 8
+console.log(binarySearch(arr, 2))  // 1
+console.log(binarySearch(arr, 7))  // 6
+console.log(binarySearch(arr, 11)) // -1
+
+console.log(binarySearch(arr, 3))  // 2
+console.log(binarySearch(arr, 3))  // 2
+console.log(binarySearch(arr, 3))  // 2
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
@@ -147,4 +147,7 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
 - [BurnzZ](https://github.com/BurnzZ)
 - [FernandaOchoa](https://github.com/FernandaOchoa)
 - [npcoder2k14](https://github.com/npcoder2k14)
-- [Jaernbrand](https://github.com/Jaernbrand)
+- [Jaernbrand](https://github.com/Jaernbrand)
+- [DiegoVicen](https://github.com/DiegoVicen)
+- [Ashwin-Kapes](https://github.com/Ashwin-Kapes)
+- [Judar Lima](https://github.com/judarlima)
diff --git a/Fibonacci/Java/Fibonacci-Recursive.java b/Fibonacci/Java/Fibonacci-Recursive.java
@@ -0,0 +1,17 @@
+class FibonacciRecursion{  
+ static int a = 0,b = 1,c = 0;    
+ static void printFibonacci(int count){    
+    if(count > 0){    
+         c = a + b;    
+         a = b;    
+         b = c;    
+         System.out.print(" " + c);   
+         printFibonacci(count - 1);    
+     }    
+ }    
+ public static void main(String args[]){    
+  int count = 10;    
+  System.out.print(a + " " + b);    
+  printFibonacci(count - 2);   
+ }  
+} 
diff --git a/Fibonacci/Swift/Fibonacci.swift b/Fibonacci/Swift/Fibonacci.swift
@@ -0,0 +1,5 @@
+//Recursive algorithm
+func fibonacci(_ n: Int) -> Int {
+    guard n != 0, n != 1 else { return n }
+    return fibonacci(n - 1) + fibonacci(n - 2)
+}
diff --git a/LinearSearch/Go/linear_search.go b/LinearSearch/Go/linear_search.go
@@ -0,0 +1,13 @@
+package search
+
+// LinearSearch returns the index of the given key found on the list.
+// It returns a value of -1 if the key doesn't exist
+func LinearSearch(list []int, key int) int {
+	for index, element := range list {
+		if key == element {
+			return index
+		}
+	}
+
+	return -1
+}
diff --git a/LinearSearch/Go/linear_search_test.go b/LinearSearch/Go/linear_search_test.go
@@ -0,0 +1,35 @@
+package search
+
+import "testing"
+
+func TestLinearSearch(t *testing.T) {
+	var tests = []struct {
+		input  []int
+		key    int
+		output int
+	}{
+		{
+			input:  []int{1, 2, 3, 4, 5},
+			key:    3,
+			output: 2,
+		},
+		{
+			input:  []int{-1, 0, 100, 33, 44},
+			key:    -2,
+			output: -1,
+		},
+		{
+			input:  []int{},
+			output: -1,
+		},
+	}
+
+	for _, test := range tests {
+		result := LinearSearch(test.input, test.key)
+
+		if result != test.output {
+			t.Errorf("LinearSearch(%v, %v) => %v, want %v",
+				test.input, test.key, result, test.output)
+		}
+	}
+}
diff --git a/QuickSort/Rust/quicksort.rs b/QuickSort/Rust/quicksort.rs
@@ -0,0 +1,43 @@
+mod sort {
+
+    pub fn quicksort<T: Ord>(arr: &mut [T]) {
+        let length = arr.len();
+        quicksort_step(arr, 0, (length as isize) - 1);
+    }
+
+
+    fn quicksort_step<T: Ord>(arr: &mut [T], lo: isize, hi: isize) {
+        if lo < hi {
+            let pivot = lomuto_partiton(arr, lo, hi);
+            quicksort_step(arr, lo, pivot - 1);
+            quicksort_step(arr, pivot + 1, hi);
+        }
+    }
+
+    fn lomuto_partiton<T: Ord>(arr: &mut [T], lo: isize, hi: isize) -> isize {
+        let mut i = lo - 1;
+        let mut j = lo;
+
+        while j < hi - 1 {
+            if arr[j as usize] < arr[hi as usize] {
+                i = i + 1;
+                arr.swap(i as usize, j as usize);
+            }
+            j = j + 1;
+        }
+
+        if arr[hi as usize] < arr[(i + 1) as usize] {
+            arr.swap(hi as usize, (i + 1) as usize);
+        }
+
+        return i + 1;
+    }
+}
+
+fn main() {
+    let mut arr = [3, 7, 8, 5, 2, 1, 9, 5, 4];
+
+    sort::quicksort(&mut arr);
+
+    println!("{:?}", arr);
+}
diff --git a/README.md b/README.md
@@ -1,4 +1,4 @@
-# Algorithms Example
+&#65279;# Algorithms Example
 
 This repository contains examples of various algorithms which were written on different programming languages.
 
@@ -25,20 +25,20 @@ EditDistance |  | :+1: |  |  | :+1: |  |  |  |
 Edmonds-Karp | :+1: |  |  |  |  |  |  |  |
 ElevatorAlgorithm | :+1: |  |  |  |  |  |  |  |
 Fast Fourier Transform |  |  |  |  | :+1: |  |  |  |
-Fibonacci | :+1: | :+1: |  | :+1: | :+1: | :+1: |  | :+1: | :+1: |  |
+Fibonacci | :+1: | :+1: |  | :+1: | :+1: | :+1: |  | :+1: | :+1: | :+1: |
 FisherYatesShuffle | :+1: |  |  |  | :+1: | :+1: |  | :+1: |
 FloodFill Algorithm | :+1: | | | | | | | |
 Floyd'sAlgorithm | :+1: | :+1: |  |  | :+1: |  |  |  |
 GreatestCommonDivisor | :+1: |:+1:| :+1: | :+1: | :+1: |   |  |  |
 HammingDistance | :+1: | :+1: |  | :+1: |  | :+1: | :+1: |  |
 HeapSort | :+1: | :+1: |  |  | :+1: | :+1: | :+1: |  | :+1:
 HistogramEqualization | :+1: |  |  |  |  |  |  |  |
-InsertionSort | :+1: | :+1: | :+1: | :+1: | :+1:  |  | :+1: | :+1: | :+1:
+InsertionSort | :+1: | :+1: | :+1: | :+1: | :+1:  | :+1: | :+1: | :+1: | :+1:
 Inverse Fast Fourier Transform |  |  |  |  | :+1: |  |  |  |
 Johnson algorithm | :+1: | :+1: |  |  | :+1: |  |  |  |
 Kadane's algorithm | :+1: | :+1: |  | :+1: | :+1: | :+1: | :+1: |  |
 Knuth Morris Prath Algorithm | :+1: | :+1: |  |  | :+1: |  |  |  |
-LinearSearch | :+1: | :+1: |  |  :+1:| :+1: | :+1: |  |  |  | :+1: |
+LinearSearch | :+1: | :+1: |  |  :+1:| :+1: | :+1: | :+1: |  |  | :+1: |
 Longest-Common-Subsequence | :+1: | :+1: |  | :+1: | :+1: |  |  |  | :+1:
 Longest-Increasing-Subsequence | :+1: | :+1: |  |  | :+1: |  |  |  |
 LongestPath |  |  |  |  | :+1: |  |  |  |
@@ -47,7 +47,7 @@ MiniMaxWithABPruning | :+1: |  |  |  |  |  |  |  |
 Modified_Binary_Search |  |  |  | :+1: |  |  |  |  |
 Pearson Hashing | :+1: |  |  |  |  |  |  |  |
 Postman Sort |  |  |  | :+1: |  |  |  |  |
-Quick Sort | :+1: | :+1: |  |  |  | :+1: | :+1: | :+1: |  :+1: |  :+1: |
+Quick Sort | :+1: | :+1: | :+1: |  |  | :+1: | :+1: | :+1: |  :+1: |  :+1: |
 Quick Select | :+1: | :+1: |  | :+1: |  |  | :+1: | |  
 Uniform-cost search | :+1: |  |  |  |  | :+1: | :+1: |  |
 RadixSort | :+1: | :+1: |  |  | :+1: |  |  |  |
@@ -61,6 +61,7 @@ TernarySearch | :+1: |:+1:  |  | :+1: | :+1: |  |  |  |
 Topological Sort |  |  |  |  | :+1: |  |  |  |  
 Segmented Sieve |:+1:| :+1: |  |  | :+1: |  |  |  |  
 Union Find |:+1:|:+1:|  | :+1: |  |  |  |  |  
+Xor swap |:+1:|  |  |  |  |  |  |  |
 
 
 ### List of Algorithms :
@@ -769,7 +770,7 @@ Union Find |:+1:|:+1:|  | :+1: |  |  |  |  |
 
 * Xiaolin Wu's line algorithm    :    algorithm for line antialiasing.
 
-* Xor swap algorithm    :    swaps the values of two variables without using a buffer
+* [Xor swap algorithm](XorSwap)    :    swaps the values of two variables without using a buffer
 
 * Yamartino method    :    calculate an approximation to the standard deviation &sigma;&theta; of wind direction &theta; during a single pass through the incoming data
 
@@ -781,6 +782,8 @@ Union Find |:+1:|:+1:|  | :+1: |  |  |  |  |
 
 * Union Find : used to know if there is a path between 2 objects or not
 
+* Fibonacci Recursive : Fibonacci series printed using Java Recursion
+
 Folder structure should be
 [**Algorithm name**]/[**language**]/**file**
 
diff --git a/XorSwap/Java/XorSwap.java b/XorSwap/Java/XorSwap.java
@@ -0,0 +1,27 @@
+/**
+ * XOR swap is an algorithm that uses the XOR bitwise operation to swap 
+ * values of distinct variables without using a temporary variable. 
+ * 
+ * @author Atom
+ * @see <a href="https://en.wikipedia.org/wiki/XOR_swap_algorithm">XOR swap</a>
+ */
+public class XorSwap {
+	
+	public static void main(String[] args) {
+		for (int i = -1, j = 3; i <= 3; i++, j--) {
+			int x = i;
+			int y = j;
+			System.out.print("x = " + x + ", y = " + y);
+			
+			// Xor swap. Swap values without using a temporary variable
+			if (x != y) {
+				x ^= y;
+				y ^= x;
+				x ^= y;				
+			}
+			
+			System.out.println(", swap(x, y) -> x = " + x + ", y = " + y);
+		}
+	}
+
+}
