给定一个按升序排序的n个不同整数的数组，编写一个函数，返回数组中的一个固定点，如果数组中存在任何固定点，则返回-1。数组中的不动点是一个索引i，使得arr[i]等于i。请注意，数组中的整数可以是负数。 例如：
null
Input: arr[] = {-10, -5, 0, 3, 7}
Output: 3 // arr[3] == 3
Input: arr[] = {0, 2, 5, 8, 17}
Output: 0 // arr[0] == 0
Input: arr[] = {-10, -5, 3, 4, 7, 9}
Output: -1 // No Fixed Point
方法1（线性搜索） 线性搜索索引i，使arr[i]==i。返回找到的第一个这样的索引。感谢pm提出这个解决方案。
C++
// C++ program to check fixed point // in an array using linear search #include <bits/stdc++.h> using namespace std; int linearSearch( int arr[], int n) { int i; for (i = 0; i < n; i++) { if (arr[i] == i) return i; } /* If no fixed point present then return -1 */ return -1; } /* Driver code */ int main() { int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Fixed Point is " << linearSearch(arr, n); return 0; } // This is code is contributed by rathbhupendra |
C
// C program to check fixed point // in an array using linear search #include <stdio.h> int linearSearch( int arr[], int n) { int i; for (i = 0; i < n; i++) { if (arr[i] == i) return i; } /* If no fixed point present then return -1 */ return -1; } /* Driver program to check above functions */ int main() { int arr[] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Fixed Point is %d" , linearSearch(arr, n)); getchar (); return 0; } |
JAVA
// Java program to check fixed point // in an array using linear search class Main { static int linearSearch( int arr[], int n) { int i; for (i = 0 ; i < n; i++) { if (arr[i] == i) return i; } /* If no fixed point present then return -1 */ return - 1 ; } // main function public static void main(String args[]) { int arr[] = { - 10 , - 1 , 0 , 3 , 10 , 11 , 30 , 50 , 100 }; int n = arr.length; System.out.println( "Fixed Point is " + linearSearch(arr, n)); } } |
Python3
# Python program to check fixed point # in an array using linear search def linearSearch(arr, n): for i in range (n): if arr[i] is i: return i # If no fixed point present then return -1 return - 1 # Driver program to check above functions arr = [ - 10 , - 1 , 0 , 3 , 10 , 11 , 30 , 50 , 100 ] n = len (arr) print ( "Fixed Point is " + str (linearSearch(arr, n))) # This code is contributed by Pratik Chhajer |
C#
// C# program to check fixed point // in an array using linear search using System; class GFG { static int linearSearch( int [] arr, int n) { int i; for (i = 0; i < n; i++) { if (arr[i] == i) return i; } /* If no fixed point present then return -1 */ return -1; } // Driver code public static void Main() { int [] arr = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; int n = arr.Length; Console.Write( "Fixed Point is " + linearSearch(arr, n)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to check fixed point // in an array using linear search function linearSearch( $arr , $n ) { for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] == $i ) return $i ; } // If no fixed point present then // return -1 return -1; } // Driver Code $arr = array (-10, -1, 0, 3, 10, 11, 30, 50, 100); $n = count ( $arr ); echo "Fixed Point is " . linearSearch( $arr , $n ); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript program to check fixed point // in an array using linear search function linearSearch(arr, n) { let i; for (i = 0; i < n; i++) { if (arr[i] == i) return i; } /* If no fixed point present then return -1 */ return -1; } // Driver Code let arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]; let n = arr.length; document.write( "Fixed Point is " + linearSearch(arr, n)); </script> |
输出：
Fixed Point is 3
时间复杂度：O（n） 方法2（二进制搜索） 首先检查中间元素是否为固定点。如果是，则将其退回；否则，如果中间+1元素的索引小于或等于高索引处的值，则固定点可能位于中间点的右侧（显然只有在存在固定点的情况下）。同样，检查中间-1元素的索引是否大于或等于低索引的值，则固定点可能位于中间点的左侧。
C++
// C++ program to check fixed point // in an array using binary search #include <bits/stdc++.h> using namespace std; int binarySearch( int arr[], int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; if (mid == arr[mid]) return mid; int res = -1; if (mid + 1 <= arr[high]) res = binarySearch(arr, (mid + 1), high); if (res != -1) return res; if (mid - 1 >= arr[low]) return binarySearch(arr, low, (mid - 1)); } /* Return -1 if there is no Fixed Point */ return -1; } /* Driver code */ int main() { int arr[10] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "Fixed Point is " << binarySearch(arr, 0, n - 1); return 0; } // This code is contributed by Ashutosh Singh |
C
// C program to check fixed point // in an array using binary search #include <stdio.h> int binarySearch( int arr[], int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; if (mid == arr[mid]) return mid; int res = -1; if (mid + 1 <= arr[high]) res = binarySearch(arr, (mid + 1), high); if (res != -1) return res; if (mid - 1 >= arr[low]) return binarySearch(arr, low, (mid - 1)); } /* Return -1 if there is no Fixed Point */ return -1; } /* Driver program to check above functions */ int main() { int arr[10] = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "Fixed Point is %d" , binarySearch(arr, 0, n - 1)); getchar (); return 0; } |
JAVA
// Java program to check fixed point // in an array using binary search class Main { static int binarySearch( int arr[], int low, int high) { if (high >= low) { int mid = low + (high - low) / 2 ; if (mid == arr[mid]) return mid; int res = - 1 ; if (mid + 1 <= arr[high]) res = binarySearch(arr, (mid + 1 ), high); if (res != - 1 ) return res; if (mid - 1 >= arr[low]) return binarySearch(arr, low, (mid - 1 )); } /* Return -1 if there is no Fixed Point */ return - 1 ; } // main function public static void main(String args[]) { int arr[] = { - 10 , - 1 , 0 , 3 , 10 , 11 , 30 , 50 , 100 }; int n = arr.length; System.out.println( "Fixed Point is " + binarySearch(arr, 0 , n - 1 )); } } |
Python3
# Python program to check fixed point # in an array using binary search def binarySearch(arr, low, high): if high > = low : mid = low + (high - low) / / 2 if mid = = arr[mid]: return mid res = - 1 if mid + 1 < = arr[high]: res = binarySearch(arr, (mid + 1 ), high) if res ! = - 1 : return res if mid - 1 > = arr[low]: return binarySearch(arr, low, (mid - 1 )) # Return -1 if there is no Fixed Point return - 1 # Driver program to check above functions */ arr = [ - 10 , - 1 , 0 , 3 , 10 , 11 , 30 , 50 , 100 ] n = len (arr) print ( "Fixed Point is " + str (binarySearch(arr, 0 , n - 1 ))) |
C#
// C# program to check fixed point // in an array using binary search using System; class GFG { static int binarySearch( int [] arr, int low, int high) { if (high >= low) { int mid = low + (high - low) / 2; if (mid == arr[mid]) return mid; int res = -1; if (mid + 1 <= arr[high]) res = binarySearch(arr, (mid + 1), high); if (res != -1) return res; if (mid - 1 >= arr[low]) return binarySearch(arr, low, (mid - 1)); } /* Return -1 if there is no Fixed Point */ return -1; } // Driver code public static void Main() { int [] arr = { -10, -1, 0, 3, 10, 11, 30, 50, 100 }; int n = arr.Length; Console.Write( "Fixed Point is " + binarySearch(arr, 0, n - 1)); } } |
PHP
<?php // PHP program to check fixed point // in an array using binary search function binarySearch( $arr , $low , $high ) { if ( $high >= $low ) { $mid = (int)( $low + ( $high - $low )/2); if ( $mid == $arr [ $mid ]) return $mid ; $res = -1; if ( $mid +1 <= $arr [ $high ]) $res = binarySearch( $arr , ( $mid + 1), $high ); if ( $res !=-1) return $res ; if ( $mid -1 >= $arr [ $low ]) return binarySearch( $arr , $low , ( $mid -1)); } /* Return -1 if there is no Fixed Point */ return -1; } // Driver Code $arr = array (-10, -1, 0, 3, 10, 11, 30, 50, 100); $n = count ( $arr ); echo "Fixed Point is: " . binarySearch( $arr , 0, $n - 1); ?> |
Javascript
<script> // javascript program to check fixed point // in an array using binary search function binarySearch(arr,low,high) { if (high >= low) { let mid = math.floor(low + (high - low)/2); if (mid == arr[mid]) return mid; let res = -1; if (mid+1 <= arr[high]) res = binarySearch(arr, (mid + 1), high); if (res!=-1) return res; if (mid-1 >= arr[low]) return binarySearch(arr, low, (mid -1)); } /* Return -1 if there is no Fixed Point */ return -1; } // Driver program let arr = [-10, -1, 0, 3, 10, 11, 30, 50, 100]; let n = arr.length; document.write( "Fixed Point is " + binarySearch(arr, 0, n-1)); </script> |
输出：
Fixed Point is 3
算法范式：分而治之 时间复杂度：O（Logn）
在给定数组中查找固定点（值等于索引）|允许重复 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
