search
HomeJavajavaTutorialFinding an Element in an Infinite Array Using Java

Finding an Element in an Infinite Array Using Java

Problem Statement

Given an infinite array of sorted integers, we need to find the index of a given target number. The array is "infinite," meaning we cannot determine its size in advance, so we can't just apply a traditional binary search directly.


Approach Overview

  1. Start with a small range: Initially, assume that the element lies within a small range (say, between indices 0 and 1).

  2. Dynamically increase the range: If the target element is not found in the initial range, we double the size of the range to search further. This exponential growth allows us to quickly hone in on the range where the target might be located.

  3. Binary search within the range: Once we determine a suitable range that contains the target, we apply binary search to efficiently find the target's index.


The Code

public class InfiniteArraySearch {
    public static void main(String[] args) {
        // Define the array (for demonstration purposes, treat this as infinite)
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};  
        int target = 6;

        // Call the function to find the target element
        int result = findElementInInfiniteArray(arr, target);
        System.out.println("Element found at index: " + result);
    }

    // Function to find the target in the infinite array
    static int findElementInInfiniteArray(int[] arr, int target) {
        // Start with a small range
        int start = 0;
        int end = 1;

        // Dynamically increase the range until the target is within bounds
        while (target > arr[end]) {
            int newStart = end + 1;  // Update start to one after the current end
            end = end + (end - start + 1) * 2;  // Double the range
            start = newStart;  // Move the start to newStart
        }

        // Perform binary search within the determined range
        return binarySearch(arr, target, start, end);
    }

    // Standard binary search implementation
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start  arr[mid]) {
                start = mid + 1;  // Move the start to the right
            } else {
                return mid;  // Element found
            }
        }
        return -1;  // Element not found
    }
}

Explanation of the Code

1. Main Function

The main function defines an example array arr and a target value 6. For simplicity, we assume the array is finite here, but conceptually, we treat it as infinite. The main function then calls findElementInInfiniteArray to search for the target, and prints the index if found.

2. Range Expansion (Linearly Expanding the Search Area)

In the findElementInInfiniteArray method:

  • We begin by assuming that the element lies within the range [0, 1].
  • If the target is greater than the value at arr[end], it means the target is not within the current range. So, we expand the range exponentially by doubling it (end = end + (end - start + 1) * 2). This effectively allows us to cover more ground in each iteration.

3. Binary Search

Once we know that the target must lie between start and end, we perform a standard binary search. Binary search is an efficient way to search in sorted arrays, as it reduces the search space by half at each step. The key comparisons are:

  • If the target is less than the middle element (arr[mid]), search the left half.
  • If the target is greater, search the right half.
  • If the target matches the middle element, return its index.

4. Edge Cases

  • If the target is smaller than the smallest element in the array, or if the array doesn't contain the target at all, the algorithm will return -1.

Time Complexity

  1. Range Expansion: The range doubles with each iteration, so it takes O(log N) operations to find the right range where the target lies.

  2. Binary Search: Once the range is found, binary search runs in O(log M), where M is the size of the range.

Thus, the overall time complexity is approximately O(log N + log M).

The above is the detailed content of Finding an Element in an Infinite Array Using Java. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
How does IntelliJ IDEA identify the port number of a Spring Boot project without outputting a log?How does IntelliJ IDEA identify the port number of a Spring Boot project without outputting a log?Apr 19, 2025 pm 11:45 PM

Start Spring using IntelliJIDEAUltimate version...

How to elegantly obtain entity class variable names to build database query conditions?How to elegantly obtain entity class variable names to build database query conditions?Apr 19, 2025 pm 11:42 PM

When using MyBatis-Plus or other ORM frameworks for database operations, it is often necessary to construct query conditions based on the attribute name of the entity class. If you manually every time...

How to use the Redis cache solution to efficiently realize the requirements of product ranking list?How to use the Redis cache solution to efficiently realize the requirements of product ranking list?Apr 19, 2025 pm 11:36 PM

How does the Redis caching solution realize the requirements of product ranking list? During the development process, we often need to deal with the requirements of rankings, such as displaying a...

How to safely convert Java objects to arrays?How to safely convert Java objects to arrays?Apr 19, 2025 pm 11:33 PM

Conversion of Java Objects and Arrays: In-depth discussion of the risks and correct methods of cast type conversion Many Java beginners will encounter the conversion of an object into an array...

How do I convert names to numbers to implement sorting and maintain consistency in groups?How do I convert names to numbers to implement sorting and maintain consistency in groups?Apr 19, 2025 pm 11:30 PM

Solutions to convert names to numbers to implement sorting In many application scenarios, users may need to sort in groups, especially in one...

E-commerce platform SKU and SPU database design: How to take into account both user-defined attributes and attributeless products?E-commerce platform SKU and SPU database design: How to take into account both user-defined attributes and attributeless products?Apr 19, 2025 pm 11:27 PM

Detailed explanation of the design of SKU and SPU tables on e-commerce platforms This article will discuss the database design issues of SKU and SPU in e-commerce platforms, especially how to deal with user-defined sales...

How to set the default run configuration list of SpringBoot projects in Idea for team members to share?How to set the default run configuration list of SpringBoot projects in Idea for team members to share?Apr 19, 2025 pm 11:24 PM

How to set the SpringBoot project default run configuration list in Idea using IntelliJ...

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software