Interview Question
Country: United States
If we plot (i, arr[i]) on a graph and assuming that these points are collinear, then this solution works only if the slope of this line is >1. It does not consider the case when the slope of this line is positive but less than 1. The fact that the array is sorted in ascending order just says that the slope is positive .. it could be either >1 or < 1.
I think the code needs to be modified as follows:
public static int findIndex(int[] arr) {
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == m) {
return m;
}
if ( ((arr[r] > r) && (arr[m] > m)) ||
((arr[r] < r) && (arr[m] < m)) ) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
@Ricky consider three cases:
1) a[m] == m - this is what we want to get if this condition is met the index is returned.
2) arr[m] > m e.g. {0,1,5,6,7} - a[3] = 5. Since we know that array is sorted and contains distinct elements we can skip the right side of the array because all elements >=3 are incorrect.
3) arr[m] < m e.g. {-2,-1,0,1,2} - a[3] = 0. We can skip the left side of the array because all elements <= 3 are incorrect.
Just like in case of binary search.
github.com/techpanja/interviewproblems/blob/master/src/arrays/indexequaltonumbersortedarray/IndexEqualToNumberSortedArray.java
public class IndexEqualToNumberSortedArray {
private IndexEqualToNumberSortedArray() {
}
/*
* Binary search. O(log N) solution.
* */
public static int indexEqualToNumberSortedArray(int[] inputArray) {
if (inputArray.length == 0) {
return -1;
}
int low = 0;
int high = inputArray.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (inputArray[mid] == mid) {
return mid;
} else if (inputArray[mid] > mid) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(indexEqualToNumberSortedArray(new int[] {1, 2, 4, 5, 6, 7}));
System.out.println(indexEqualToNumberSortedArray(new int[] {0, 3, 4, 5, 6, 7}));
System.out.println(indexEqualToNumberSortedArray(new int[] {-1, 0, 1, 2, 4, 7}));
System.out.println(indexEqualToNumberSortedArray(new int[] {-1, 0, 1, 2, 3, 5}));
System.out.println(indexEqualToNumberSortedArray(new int[] {-1, 0, 1, 3, 5, 6}));
}
}
int FindIndex(const int const* input, int len)
{
if (input == NULL || len == NULL)
return -1;
int start = 0;
int end = len - 1;
while (start <= end)
{
int pos = (start + end) / 2;
if (input[pos] < 0 || input[pos] < pos)
{
start = pos + 1;
}
else if (input[pos] > pos)
{
end = pos - 1;
}
else
{
return pos;
}
}
return -1;
}
(1)the array is in ascending order
>>> arr[i] > arr[i-1]
<=> arr[i] - arr[i-1] > 0
(2)the elements are integers
>>> arr[i] - arr[i-1] >= 1
<=> arr[i] - arr[i-1] >= i - (i-1)
<=> arr[i] - i >= arr[i-1] - (i-1)
(3)the array of arr[k]-k is in non-decesending order, so binary search works
Notice that a[i+1] - 1 >= a[i] IMPLIES a[i+1] - (i+1) >= a[i] - i. (Elements are distinct sorted)
Thus the "vitrual array" a[i] - i, is sorted, and you are basically looking for a 0.
So, do a binary search and look for 0, with the compare function which compares a[i] - i instead of a[i].
Since the array index starts from 0, initialize always arr[0] to 0 so that you dont have to bother about index incrementation.
#include <iostream>
# include <string>
using namespace std;
int ser(int* arr, int low, int high)
{
if(low > high)
return -1;
int mid = (low + high )/2;
if(arr[mid] == mid)
return mid;
return arr[mid] > mid ? ser(arr, low, mid -1) : ser(arr, mid+1, high);
}
int main()
{
int arr[11]={0,1,2,3,6,8,10,12,14,15,20};
cout<<ser(arr,1,11)<<endl;
return 0;
}
Again binary search does the job
Code
- thelineofcode February 02, 2014