CODEWITHSUNDEEP
arraysdata-structurescomplexity-theory
Avinash
Avinash

Reputation: 55

Find array subscript and value which is same

I have a sorted array of n elements. The values can be negative or positive.

The specialty of this array is that out of n elements, there is 1 particular element where a[x]=x and the rest of the data does not satisfy the condition.

Is there any better way to find such an 'x' apart from looping the entire array.

Suppose my array is [-2999,-33,0,2,4,67,654] Here a[4]=4 and the rest does not match such a criterion..

Upvotes: 1

Views: 272

Answers (2)

Soumadeep Saha
Soumadeep Saha

Reputation: 335

you can use this. This is O(N).

for(i=0;i<MAX;i++){
    if(i==array[i]){//do something}
}

If the array is sorted in descending order use

for(i=MAX-1;i>=0;i11){
    if(i==array[i]){//do something}
}

Here MAX is size of array

Upvotes: 0

CodePuppet
CodePuppet

Reputation: 191

Since the array is already sorted, you can use binary search which is O(lgn) to find the element.

You can also ignore all negative valued elements because an index cannot be negative.

http://en.wikipedia.org/wiki/Binary_search_algorithm

Upvotes: 1

Related Questions