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.

//This is a java program to perform uniform binary search.
import java.util.Random;
import java.util.Scanner;
 
public class Uniform_Binary_Search 
{
    static int N = 10;
    static int[] sequence = new int[N];
    static int[] delta = new int[42];
 
    public static void sort() 
    {
        int i, j, temp;
        for (i = 1; i < N; i++) 
        {
            j = i;
            temp = sequence[i];
            while (j > 0 && temp < sequence[j - 1]) 
            {
                sequence[j] = sequence[j - 1];
                j = j - 1;
            }
            sequence[j] = temp;
        }
    }
 
    public static void make_delta(int N) 
    {
        System.out.println();
        int power = 1;
        int i = 0;
        do 
        {
            int half = power;
            power <<= 1;
            delta[i] = (N + half) / power;
        } while (delta[i++] != 0);
    }
 
    public static int unisearch(int key) 
    {
        int i = delta[0] - 1; /* midpoint of array */
        int d = 0;
 
        while (true) 
        {
            if (key == sequence[i])
                return i;
            else if (delta[d] == 0)
                return -1;
            else 
            {
                if (key < sequence[i])
                    i -= delta[++d];
                else
                    i += delta[++d];
            }
        }
    }
 
    public static void main(String args[]) 
    {
        Random random = new Random();
 
        for (int i = 0; i < N; i++)
            sequence[i] = Math.abs(random.nextInt(100));
        System.out.println("The sequence is :");
        sort();
        for (int i = 0; i < N; i++)
            System.out.print(sequence[i] + " ");
        //sort();
        make_delta(N);
 
        System.out.println("Enter the element to be searched: ");
        Scanner sc = new Scanner(System.in);
        int key = sc.nextInt();
        int p = unisearch(key);
        if (p > 0)
            System.out.println("Element found at position " + p);
        else
            System.out.println("Element doesn't exist");
        sc.close();
    }
}

Output:

$ 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

Related posts:

How to Manually Authenticate User with Spring Security
Easy Ways to Write a Java InputStream to an OutputStream
XML Serialization and Deserialization with Jackson
Mảng (Array) trong Java
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Spring’s RequestBody and ResponseBody Annotations
Converting Between Byte Arrays and Hexadecimal Strings in Java
Comparing Objects in Java
Query Entities by Dates and Times with Spring Data JPA
Properties with Spring and Spring Boot
Hashing a Password in Java
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Composition, Aggregation, and Association in Java
Spring @RequestMapping New Shortcut Annotations
Guide to WeakHashMap in Java
Spring JDBC
Apache Tiles Integration with Spring MVC
Sử dụng JDBC API thực thi câu lệnh truy vấn dữ liệu
Java Program to Perform Encoding of a Message Using Matrix Multiplication
Java Program to Convert a Decimal Number to Binary Number using Stacks
Spring Boot - Building RESTful Web Services
Giới thiệu Google Guice – Dependency injection (DI) framework
Java Timer
Spring Boot: Customize the Jackson ObjectMapper
Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range
Spring 5 Functional Bean Registration
Java Deep Learning Essentials - Yusuke Sugomori
Zipping Collections in Java
Iterating over Enum Values in Java
Spring Data – CrudRepository save() Method
Java Program to Implement Singly Linked List
Introduction to PCollections