Algorithm for searching for a key in 1,000,000,000 elements with the key being in the first n indices without n being specified beforehand

user_14331490 0
Viewed 407

The question is as follows:

Suppose you are given a very large integer array A with 1,000,000,000 elements, with elements sorted in descending order. However, only the first n elements contain data which are positive integers, but the value of n is unknown. The rest of the array elements contain zeroes.

Give the algorithm for a method search(A,k) to search for a key k in the array A. It returns the index of the array where k is found, or -1 otherwise. Your algorithm must run in worst case O(logn) time.

You may use binarySearch(A, k, left, right) that searches for k in A[left] through A[right] (assuming left to right is sorted in descending order).

The approaches that I have thought of so far:

  1. Use a for loop to iterate from index 0 till the index containing the first 0 and compare against k. This takes O(n) time so doesn't fit the time limit.

  2. Binary search on A itself. This takes O(log 1,000,000,000) time and exceeds the time limit.

I am kind of stuck here and unable to think of any other approaches.

What would be an approach that runs in worst case O(logn)?

time-complexity algorithm
2 Answers

Hi this approach is based on a modified binary search

  1. Start at first index if matches return

  2. Double the index untill value is found or you the end

    a) if Value is greater than k continue

    b) else if value is less than k BinarySearch(index/2, index, k)

So basically what we did is we narrowed down our search space by jumping forward, Like previous answer by nice_dev; But While Jumping we also checked if our value is in specific window if it is we stop jumping and binary search the last window

user_50100280

The idea here will be to first find the value of n. We can do a jump similar to concept of jump arrays like below:

  • Start from index 1(1-based indexing).
  • If current value is not zero, jump to index * 2.
  • Repeat step 2 if current index value is not zero.
  • If current index value is zero, iterate one by one from last non zero index to find value of n.

Pseudocode:

index = 1
prev = 1
while index <= arr.length and arr[index - 1] != 0:
    prev = index
    index = index * 2

while prev <= arr.length and arr[prev - 1] != 0
    prev++

The below linear run will be minimal as you have reached the last value of n in log n time. If binarySearch routine is already provided, then you can just do binarySearch(A, k, 0, prev - 1) to get the final answer.

user_49648220
Related