Geek asks and answers

Find an element in a sorted array with infinite length

Given an array with infinite length, having both positive and negative integers. Find the element in it.

EDIT
All elements of the array are unique and the array is infinite in the right direction.

There are two approaches:

Approach 1:

Set the index at position 100, if the element to be found is smaller, the binary search in the previous 100 elements, otherwise set the next index at position 200. Thus, continue to increase the index by 100 until the element is larger.

Approach 2:

Set the power index 2. First, set the index at 2, then 4, then 8, then 16, and so on. Again, perform a binary search from position 2 ^ K to 2 ^ (K + 1), where the element is between them.

Which of the two approaches will be better both in the best case and in the worst case?

+7
source share
7 answers

The first approach will be linear in the index of the element ( O(k)where kis the index of the element). In fact, you will need k/100iterations to find an element that is larger than the element you are looking for, that is O(k).

The second approach will be logarithmic in the same index. O(logk). (where kis the index of the element). Here you will need log(k)iterations until you find a higher element. Then the binary search between 2^(i-1), 2^i(where iis the iteration number) will also be logarithmic, which will totalO(logk)

, .

+17

, .. (.. x 0, x 1,...) ele & shy; , : n, bi & shy; na & shy; ry 0,..., n & minus; x 0 > . , x i & ge; + x 0 & ge; 0.

, n log 2 (n & minus; x 0).

+3

. 2.

, B A 0, , , , A B. , , B = A A = 2 * A . O (log (M)), M - , .

+1

, . , O(1), , , , " " , O(log(k)).

, , , O(log(k)), k log(k), .

, , - O(log(k)).

, O(log(k)^2). O(k log k), .

+1

2 . , , . ? , - . , in 2^i = 2^(i+1)-2^i, log(2^i)=i. , i. , O(n) . ?

0

- , 2 ^ n ,

e.g.
 arr = 1,2,3,4,5,6,7,8,9,-1,-1,-1,-1,-1,-1...........
 num = 8;

efficiency = 2logn
0

--Complete Solution-- O (logn)

B {

public static void main(String[] args) {
    // Assuming sorted array of infinite length
    int a[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };

    int elementToFind = 12;

    int finalIndex = getFinalIndex(a, elementToFind);

    if (finalIndex == -1) {
        System.out.println("Element not found");
    }
    System.out.println("Found element:" + a[finalIndex]);

}

private static int getFinalIndex(int[] a, int elementToFind) {

    int power = 2;
    int finalIndex = (int) Math.pow(2, power);

    for (int i = 0; i < finalIndex;) {

        if (elementToFind == a[finalIndex]) {
            return finalIndex;
        }

        else if (elementToFind < a[finalIndex]) {
            System.out.println("search through binary search algo");
            // taking i as starting index in binary search call
            int searchedIndex = callToBinarySearch(a, i, finalIndex);
            return searchedIndex;
        }

        else {
            i = finalIndex + 1;
            power = power * 2;
            finalIndex = (int) Math.pow(2, power);

        }
    }
    return -1;

}

}

0

More articles:


All Articles