Thursday, October 11, 2012

Search in Array for A[i] == i

Problem: We have a sorted array of distinct elements, A. Find the occurrences of elements where A[i] == i.

Discussion: It pretty much the same problem as binary search once you realize how to divide. We know
  1. The array is distinct and sorted so, for each j, A.length >= j > i we will have A[j] > A[i]; and similarly, for each j, 1 <= j < i we will have A[j] < A[i]
  2. If we found out A[i] > i, so for all j > i we will have A[j] > j (from previous point). So no point in searching in right in this case.

    Similarly, if A[i] < i, no gain in searching  in left of i.
So, here is the algorithm
searchForAiI (A, low, high)
  if low > high
      return -1
  mid = low + (high - low)/2
  if A[mid] == mid
    return mid
  else if mid > A[mid] 
    //all the elements in right is greater than their index, so search left
    return searchForAiI (A, low, mid-1)
     //all the elements in left is smaller than their index, so search right
    return searchForAiI (A, mid+1, high)     

[1] View/download Java code from GitHub and get sample run here.

1 comment:

  1. شركة كشف تسربات المياه شرق الرياض


    شركة كشف تسربات المياه شمال الرياض


    شركة كشف تسربات المياه شمال الرياض



    شركات نقل العفش بجدة كثيرة ومتعددة والإختيار بين أسطول الشركات الموجودة صعب ويعتمد الإختيار بين شركة نقل اثاث بجدة على إسلوب المندوب ودقة المواعيد وأداء العمل ويفضل إختيار الشركات على حسب خبرتها في مجال نقل العفش وعلى جودة الأداء والأمانة لأننا نترك لهم متعلقات المنزل بين متناول أيديهم .