CareerCup

There is a O(log n) solution using binary search to eliminate half the candidates at each iteration. Let's say you're looking for A[i] = i, then for any i > 0 A[i] >= A[i-1]+1, because the array is increasingly sorted. Then imagine you've created an array A' such that each element is A[i]-i, then A' is also increasingly sorted. Therefore, you can do a binary search for 0 in A' to find the index such that A[i] = i. By the way, we'll not need to actually create A', just assume that A'[i] = A[i] -i.

Here is the code:

int findIndexEqualsValue(const vector<int> &A) {
  int l = 0, r = A.size() - 1;
  while (l <= r) {
    int m = (l+r)/2;
    int val = A[m] - m;
    if (val == 0) {
      return m;
    } else if (val > 0) {
      r = m - 1;
    } else {  // val < 0
      l = m + 1;
    }
  }
  return -1;
}

This is code runs in O(log n)

I think this can be done in O(log n) complexity. There could be three cases...

Check the first number ... arr[0] > 0 or ==0 or < 0

case 1: arr[0] > 0
answer: none
O(1)


case 2: arr[0] = 0
e.g. arr = [ 0, 1, 2, 3, 5, 6, 7, 8, 9];

Apply binary search to arr[0 to n].
if array[n/2] > n/2, reapply binary search to arr[0 to (n/2 - 1)] until we reach an equality.. and keep track of the n/2 at each step, let it be variable "tracker"..
we will reach the equality at arr[2], and tracker = 4
Now, reapply binary search to arr[n/2 to tracker] because we know that all the elements to its left suffice the condition and will be in the result set.
Continue doing this, till we reach size(arr) = 1

O(logn n)


case 3: arr[0] < 0
This is a bit complex than the above two cases.
Here we have to run binary search twice (on two sides of the array) to check what is the index where positive number starts (let it be 'm'). and then repeat the case 2 with the lower bound 'm' instead of 0.

There is no O(log N) solution. Consider the input sequence [1, 2, 3, 4, ... , n]

I suspect if this can be done in logn time.

1. Take middle element and check a[i] = i
2. If First step passed, check a[i+1]==i+1
3. if step two passed check for middle element between i and a.length and do from step1
4. if step two failed, then a[0] to a[i] , then print 0...i
5. If first step failed, check a[i-1]=i-1
6. if step five passed, then print 0... i-1
7. if step five failed check for middle term element between 0 and i-1, repeat from step 1

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace OneTake
{
    class ValueEqualToIndex
    {
        public int[] find(int[] array) {
            if (array == null || array.Length < 1) return null;
            if (array.Length == 1) {
                if (array[0] == 0) return array;
                else return null;
            }

            int? found = null;
            
            int low = 0;
            int high = array.Length - 1;
            int mid = (low + high) / 2;

            // Found array[mid] = mid;
            while (mid > low && mid < high) {
                if (array[mid] >= mid)
                {
                    if (array[mid] == mid) { 
                        found = mid;
                        break;
                    }

                    high = mid;
                    mid = (low + high) / 2;
                }
                else {
                    low = mid;
                    mid = (low + high) / 2;
                }
            }

            // Iterate from left to right, found the equal case, worst O(n)
            Queue<int> stack = new Queue<int>();
            if(found.HasValue) {
                low = found.Value - 1;
                high = found.Value;

                bool canLeft = true;
                bool canRight = true;

                while(canLeft || canRight) {
                    if(canLeft && low >= 0 &&array[low] == low) {
                        stack.Enqueue(array[low--]);
                    }
                    else {
                        canLeft = false;
                    }

                    if(canRight && high < array.Length && array[high] == high) {
                        stack.Enqueue(array[high++]);
                    }
                    else {
                        canRight = false;
                    }
                }
            }


            return stack.ToArray();
        }

        public void test() {

            int[] array = { -1, 0, 1, 2, 4, 5 };
            int[] res = find(array);

            Console.WriteLine(String.Join(",", res));
        }
    }
}

I think we can use binary search to solve this problem . The time complexity is O(log(n) + k), which k stands for the mount of
the number matching the requirement, n is totoal numbers in the array .

My divide & conquer approach:
(1) The method takes the array, starting position, ending position, and a TreeMap
(2) Each entry in the TreeMap (startPos, endPos) represents the start & end positions of a subarray that satisfies the condition
(3) First check whether array[startPos] == startPos && array[endPos] == endPos
(4) If so, that means all elements in this subarray satisfy the condition, so insert entry into TreeMap
(5) Otherwise, check if array[startPos] > startPos or array[endPos] < endPos
(6) If so, that means none of the elements in the subarray[startPos..endPos] can satisfy the condition. For instance, if startPos=0 and endPos=4 and that arr=[2,3,4,5,6], you can see how even if the array elements increase in the slowest manner, it would have still exceeded the endPos before it reaches the endPos.
(7) Otherwise, recursively check the left & right subarrays.

static void findMatching(int[] arr, int startPos, int endPos, TreeMap<Integer, Integer> matching) {
  int startValue = arr[startPos];
  int endValue = arr[endPos];
  if(startValue == startPos && endValue == endPos) {
    matching.put(startPos, endPos);
  } else if(startValue <= startPos && endValue >= endPos) {
    int middlePos = (startPos + endPos)/2;
    if(middlePos != endPos)
      findMatching(arr, startPos, middlePos, matching);
    if(middlePos+1 <= endPos)
      findMatching(arr, middlePos+1, endPos, matching); 
  }
}