Question for interview - search in sorted array X for index i such that X [i] = i

Question

I was asked the following question yesterday:

Consider a Java or C ++ array, say, X which is sorted, and it does not have two identical elements. What is the best way to find an index, say i such that the element in this index is also i . This is X[i] = i .

As an explanation, she also gave me an example:

 Array X : -3 -1 0 3 5 7 index : 0 1 2 3 4 5 Answer is 3 as X[3] = 3. 

The best I could think of was a linear search. After the interview, I thought a lot about this problem, but could not find a better solution. My argument: an element with a required property can be anywhere in the array. So it can also be at the very end of the array, so we need to check every element.

I just wanted to confirm from the community that I was right. Please tell me that I am right :)

Answer 1

This can be done in O(logN) and O(1) space 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 ascending order, the elements in the new array Y will be in non-decreasing order. So a binary search for 0 in Y will give an answer.

But creating Y will take O(N) space and O(N) time. Thus, instead of creating a new array, you simply modify the binary search so that the 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

Answer 2

Faster solutions exist that average O (log n) or, in some cases, O (log log n) instead of O (n). For a “binary search and search, ” you will probably find very good explanations.

If the array is unsorted, then yes, the element is located anywhere, and you cannot access O (n), but this does not apply to sorted arrays.

-

Some explanation of the search interpolation query:

While a binary search only deals with comparing two elements in terms of more / no more, the interpolation search also tries to use numerical values . The fact is that you have a sorted range of values ​​from 0 to, say, 20,000. You are looking for 300 - the binary search will begin in half the range, at 10,000. An interpolation search assumes that 300 is likely to be somewhere closer to 0 than 20,000, so he will check element 6000 first instead of 10000. Then again - if it is too high, write to the lower subband, and it is too low - write to the upper subband.

For a large array with + - even distribution of values, the interpolation search should behave much faster than the binary search - see this code yourself. Also, it works best if you first use one interpolation search step, then one binary search step, etc.

Note that this is what a person does intuitively when looking for something in a dictionary.

Answer 3

I think it will be faster.

Start in the middle of the list

If X [i]> i, then go to the middle of the remaining left side

if X [i] i then go to the middle of the remaining right

Keep doing this and this will reduce the number of possible elements in half for each cycle.

Answer 4

No need to think in terms of any array Y , as suggested in answer , using @codaddict.

Use a binary search and check the middle element of the given array, if it is less than its index than we do not need to check any lower index, because the array is sorted, and therefore, if we move to the left, subtract m indices and (at least) value m, all subsequent elements will also be too small. For example. if arr[5] = 4 , then arr[4] <= (4 - 1) and arr[3] <= (4 - 2) , etc. Similar logic can be applied if the middle element is larger than its index.

Here is a simple Java implementation:

 int function(int[] arr) { int low = 0; int high = arr.length - 1; while(low <= high) { int mid = high - (high - low) / 2; if(arr[mid] == mid) { return mid; } else if(arr[mid] < mid) { low = mid + 1; } else { high = mid - 1; } } return -1; // There is no such index } 

Please note that the above solution will only work if all the elements are different.

Answer 5

You can do a binary search: find the middle if the value is less than the index than no index below will contain the same value.

Then you search in the upper half and continue until you find an item, or until you reach one item.

Answer 6

Your linear search idea looks right, yes. I personally cannot think of another way to find the value if you are not sorted so that the required value is always in the first element.

EDIT: Alright, I'm wrong. I apologize!

Answer 7

This is the solution I came across and works if there are duplicates (I mistakenly overlooked this disclaimer that there are no duplicates).

 //invariant: startIndex <= i <= endIndex int modifiedBsearch(int startIndex, int endIndex) { int sameValueIndex = -1; int middleIndex = (startIndex + endIndex) /2; int middleValue = array[middleIndex]; int endValue = array[endIndex]; int startValue = array[startIndex]; if(middleIndex == middleValue) return middleValue; else { if(middleValue <= endIndex) sameValueIndex = modifiedBsearch(middleIndex + 1, endIndex) if(sameValueIndex == -1 && startValue <= middleIndex) sameValueIndex = modifiedBsearch(startIndex, middleIndex -1); } return sameValueIndex; } 

I would suggest that it takes O (log n) time, but is this not clear at first glance ???

If you're out of luck, it will take O (n log n) time (the height of the stack tree will be log n, and it will be a complete tree with n nodes at the last level, n / 2 at the end of the last, etc.).

Thus, on average it will be between O (log n) and O (n log n).

Answer 8

Yes, I think you're right. A logarithmic search is not possible, as there is no way to reduce the amount of data that we have. We will need to look at the entire index in the array.

@Kos, I don’t see how sorting an array will make any difference?

Answer 9

on the top of my head, performing binary splitting can be faster.

look at the average value, if it is high, then what you need, repeat the search in the lower half.

After one comparison, you have already missed your data set by half

Answer 10

After reading the question, it seems that there is one scenario that can be used to speed up the search. When comparing a position with a value, if the value is greater than the position, then the value can be used as the next position for valuation. This will help you jump over the array faster. This can be done because the array is sorted. The values ​​that we skip are conceptually shifted to the left in the array and are in the wrong place.

Example:

 int ABC[] = { -2, -5, 4, 7, 11, 22, 55 }; 

If my current position is 2 and it has a value of 4, they are not equal and conceptually the value of 4 is shifted to the left. I can use the value 4 as the next position, because if the value 4 is out of position, then all less than 4 is also out of position.

Some sample code is for discussion only:

 void main() { int X[] = { -3, -1, 0, 3, 5, 7}; int length = sizeof(X)/sizeof(X[0]); for (int i = 0; i < length;) { if (X[i] > i && X[i] < length) i = X[i]; // Jump forward! else if (X[i] == i) { printf("found it %i", i); break; } else ++i; } } 

Answer 11

A modified version of binary search is sufficient, I think,

Assume the sequence

 Array : -1 1 4 5 6 Index : 0 1 2 3 4 Result : 1 

or

 Array : -2 0 1 2 4 6 10 Index : 0 1 2 3 4 5 6 Result: 4 

From both examples it is clear that the desired result will never lie on the right side if the middle <[mid] ... the pseudocode will look something like this.

 mid <- (first + last )/2 if a[mid] == mid then return mid else if a[mid] < mid then recursive call (a,mid+1,last) else recursive call (a,first,mid-1) 

Answer 12

Java:

 public static boolean check (int [] array, int i) { if (i < 0 || i >= array.length) return false; return (array[i] == i); } 

C ++:

 bool check (int array[], int array_size, int i) { if (i < 0 || i >= array_size) return false; return (array[i] == i); }