Java Program to Perform Uniform Binary Search

«
»
This is a java program to perform uniform binary search technique. It uses a lookup table to update a single array index, rather than taking the midpoint of an upper and a lower bound on each iteration; therefore, it is optimized for architectures (such as Knuth’s MIX) on which a table look-up is generally faster than an addition and a shift, and many searches will be performed on the same array, or on several arrays of the same length.

Here is the source code of the Java Program to Perform Uniform Binary Search. 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 perform uniform binary search.
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. public class Uniform_Binary_Search 
  6. {
  7.     static int N = 10;
  8.     static int[] sequence = new int[N];
  9.     static int[] delta = new int[42];
  10.  
  11.     public static void sort() 
  12.     {
  13.         int i, j, temp;
  14.         for (i = 1; i < N; i++) 
  15.         {
  16.             j = i;
  17.             temp = sequence[i];
  18.             while (j > 0 && temp < sequence[j - 1]) 
  19.             {
  20.                 sequence[j] = sequence[j - 1];
  21.                 j = j - 1;
  22.             }
  23.             sequence[j] = temp;
  24.         }
  25.     }
  26.  
  27.     public static void make_delta(int N) 
  28.     {
  29.         System.out.println();
  30.         int power = 1;
  31.         int i = 0;
  32.         do 
  33.         {
  34.             int half = power;
  35.             power <<= 1;
  36.             delta[i] = (N + half) / power;
  37.         } while (delta[i++] != 0);
  38.     }
  39.  
  40.     public static int unisearch(int key) 
  41.     {
  42.         int i = delta[0] - 1; /* midpoint of array */
  43.         int d = 0;
  44.  
  45.         while (true) 
  46.         {
  47.             if (key == sequence[i])
  48.                 return i;
  49.             else if (delta[d] == 0)
  50.                 return -1;
  51.             else 
  52.             {
  53.                 if (key < sequence[i])
  54.                     i -= delta[++d];
  55.                 else
  56.                     i += delta[++d];
  57.             }
  58.         }
  59.     }
  60.  
  61.     public static void main(String args[]) 
  62.     {
  63.         Random random = new Random();
  64.  
  65.         for (int i = 0; i < N; i++)
  66.             sequence[i] = Math.abs(random.nextInt(100));
  67.         System.out.println("The sequence is :");
  68.         sort();
  69.         for (int i = 0; i < N; i++)
  70.             System.out.print(sequence[i] + " ");
  71.         //sort();
  72.         make_delta(N);
  73.  
  74.         System.out.println("Enter the element to be searched: ");
  75.         Scanner sc = new Scanner(System.in);
  76.         int key = sc.nextInt();
  77.         int p = unisearch(key);
  78.         if (p > 0)
  79.             System.out.println("Element found at position " + p);
  80.         else
  81.             System.out.println("Element doesn't exist");
  82.         sc.close();
  83.     }
  84. }

Output:

advertisement
$ javac Uniform_Binary_Search.java
$ java Uniform_Binary_Search
 
The sequence is :
12 13 20 24 27 32 63 64 74 82 
Enter the element to be searched: 
24
Element found at position 3
 
The sequence is :
0 30 31 32 37 48 51 58 78 87 
Enter the element to be searched: 
98
Element doesn't exist

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 & technical discussions at Telegram SanfoundryClasses.