GeezerVison is showing github.com — Java/Programs/Fibonacci.java at main · Koder-Sunil/Java

Expand file tree

Fibonacci.java

Copy path

More file actions

Latest commit

History

65 lines (54 loc) · 1.17 KB

Fibonacci.java

Copy path

File metadata and controls

65 lines (54 loc) · 1.17 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

// Java program for Fibonacci Search

import java.util.*;

class Fibonacci {

public static int min(int x, int y)

{

return (x <= y) ? x : y;

}

/* Returns index of x if present, else returns -1 */

public static int fibMonaccianSearch(int arr[], int x,

int n)

{

/* Initialize fibonacci numbers */

int fibMMm2 = 0;

int fibMMm1 = 1;

int fibM = fibMMm2 + fibMMm1;

while (fibM < n) {

fibMMm2 = fibMMm1;

fibMMm1 = fibM;

fibM = fibMMm2 + fibMMm1;

}

int offset = -1;

while (fibM > 1) {

int i = min(offset + fibMMm2, n - 1);

if (arr[i] < x) {

fibM = fibMMm1;

fibMMm1 = fibMMm2;

fibMMm2 = fibM - fibMMm1;

offset = i;

}

else if (arr[i] > x) {

fibM = fibMMm2;

fibMMm1 = fibMMm1 - fibMMm2;

fibMMm2 = fibM - fibMMm1;

}

else

return i;

}

if (fibMMm1 == 1 && arr[n-1] == x)

return n-1;

return -1;

}

public static void main(String[] args)

{

int arr[] = { 10, 22, 35, 40, 45, 50,

80, 82, 85, 90, 100,235};

int n = 12;

int x = 235;

int ind = fibMonaccianSearch(arr, x, n);

if(ind>=0)

System.out.print("Found at index: "+ ind);

else

System.out.print(x+" isn't present in the array");

}