Java Program to Search Sorted Sequence using Divide and Conquer

This is a java program to search a number using Fibonacci Sequence. The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search, Fibonacci search examines locations whose addresses have lower dispersion. Therefore, when the elements being searched have non-uniform access memory storage (i.e., the time needed to access a storage location varies depending on the location previously accessed), the Fibonacci search has an advantage over binary search in slightly reducing the average time needed to access a storage location. The typical example of non-uniform access storage is that of a magnetic tape, where the time to access a particular element is proportional to its distance from the element currently under the tape’s head. Note, however, that large arrays not fitting in cache or even in RAM can also be considered as non-uniform access examples. Fibonacci search has a complexity of O(log(x)).

Here is the source code of the Java Program to Search Number Using Divide and Conquer with the Aid of Fibonacci Numbers. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to search an element using Fibonacci search
  2. import java.util.Scanner;
  3.  
  4. public class Fibonacci_Search 
  5. {
  6.     static int kk = -1, nn = -1;
  7.     static int fib[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,
  8.             377, 610, 98, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,
  9.             75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309,
  10.             3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
  11.             102334155, 165580141 };
  12.  
  13.     static int fibsearch(int a[], int n, long x) 
  14.     {
  15.         int inf = 0, pos, k;
  16.         if (nn != n) 
  17.         {
  18.             k = 0;
  19.             while (fib[k] < n)
  20.                 k++;
  21.             kk = k;
  22.             nn = n;
  23.         }
  24.         else
  25.             k = kk;
  26.  
  27.         while (k > 0) 
  28.         {
  29.             pos = inf + fib[--k];
  30.             if ((pos >= n) || (x < a[pos]))
  31.                 ;
  32.             else if (x > a[pos]) 
  33.             {
  34.                 inf = pos + 1;
  35.                 k--;
  36.             }
  37.             else 
  38.                 return pos;
  39.         }
  40.         return -1;
  41.     }
  42.  
  43.     public static void main(String args[]) 
  44.     {
  45.         int arr[] = { 2, 3, 45, 56, 67, 78, 89, 99, 100, 101 };
  46.         int num, pos;
  47.         Scanner scan = new Scanner(System.in);
  48.         System.out.println("Enter an element to search: ");
  49.         num = scan.nextInt();
  50.         pos = fibsearch(arr, 10, num);
  51.         if (pos >= 0)
  52.             System.out.println("\nElement is at index : "
  53.                     + fibsearch(arr, 10, num));
  54.         else
  55.             System.out.println("\nElement NOT found!! ");
  56.         scan.close();
  57.     }
  58. }

Output:

$ javac Fibonacci_Search.java
$ java Fibonacci_Search
 
Enter an element to search: 
78
 
Element is at index : 5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.