You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
17 lines
374 B
Ruby
17 lines
374 B
Ruby
5 years ago
|
=begin
|
||
|
Given an array, find a fixed point in the array.
|
||
|
Fixed Point in an array is an index i such that arr[i] is equal to i, i.e. a[i]==i
|
||
|
Time-complexity: O(n)
|
||
|
Space-complexity: O(1)
|
||
|
Algorithm: Linear Search
|
||
|
=end
|
||
|
def fixed_point(a)
|
||
|
n=a.length
|
||
|
for i in 0...n
|
||
|
if a[i]==i
|
||
|
return i
|
||
|
end
|
||
|
end
|
||
|
#if no fixed point exists
|
||
|
return -1
|
||
|
end
|