Interview question – Search in sorted array X for index i such that X[i] = i

by

This can be done in O(logN) time and O(1) space by using a slightly modified binary search.

Consider a new array Y such that Y[i] = X[i] - i

Array X : -3 -1   0  3  5  7
index   :  0  1   2  3  4  5
Array Y : -3 -2  -2  0  1  2

Since the elements in X are in increasing order, the elements in the
new array Y will be in non-decreasing order. So a binary
search for 0 in Y will give the answer.

But creating Y will take O(N) space and O(N) time. So instead of
creating the new array you just modify the binary search such that a
reference to Y[i] is replaced by X[i] - i.

Algorithm:

function (array X) 
       low  = 0
       high = (num of elements in X) - 1

       while(low <= high) 
               mid = (low + high) / 2

               // change X[mid] to X[mid] - mid
               if(X[mid] - mid == 0)
                       return mid

               // change here too
               else if(X[mid] - mid < 0)
                       low = mid + 1;

               else
                       high = mid - 1;
       end while

       return -1 // no such index exists...return an invalid index.

end function

Java implementation

C++ implementation

More Related Contents:

  1. How to remove repetition in output results in this code
  2. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  3. Finding the max/min value in an array of primitives using Java
  4. Permutation of array
  5. Connect 4 check for a win algorithm
  6. Quickest way to find missing number in an array of numbers
  7. Finding the second highest number in array
  8. Java, find intersection of two arrays
  9. Java, Shifting Elements in an Array
  10. Find duplicate element in array in time O(n)
  11. All possible combinations of an array
  12. How do I get the intersection between two arrays as a new array?
  13. Flatten nested arrays in java
  14. How to find the only number in an array that doesn’t occur twice [duplicate]
  15. Generate Random Numbers in Array [duplicate]
  16. find an element in a sorted matrix [duplicate]
  17. Algorithm – How to delete duplicate elements in a list efficiently?
  18. Finding the median value of an array?
  19. Java Array, Finding Duplicates
  20. Effective gif/image color quantization?
  21. How can I convert int[] to Integer[] in Java?
  22. Picking a random element from a set
  23. Get only part of an Array in Java? [duplicate]
  24. byte array to short array and back again in java
  25. Java creating byte array whose size is represented by a long
  26. Generating Java interface with SWIG
  27. Difference between Arrays.sort() and Arrays.parallelSort()
  28. Finding an element in an array in Java
  29. Java Iterate Bits in Byte Array
  30. How to convert JSONArray to List with Gson?

Leave a Comment