Question

Formatted question description: https://leetcode.ca/all/1064.html

 1064. Fixed Point

 Given an array A of distinct integers sorted in ascending order,
 return the smallest index i that satisfies A[i] == i.  Return -1 if no such i exists.


 Example 1:

 Input: [-10,-5,0,3,7]
 Output: 3
 Explanation:
 For the given array, A[0] = -10, A[1] = -5, A[2] = 0, A[3] = 3, thus the output is 3.


 Example 2:

 Input: [0,2,5,8,17]
 Output: 0
 Explanation:
 A[0] = 0, thus the output is 0.


 Example 3:

 Input: [-10,-5,3,4,7,9]
 Output: -1
 Explanation:
 There is no such i that A[i] = i, thus the output is -1.


 Note:

 1 <= A.length < 10^4
 -10^9 <= A[i] <= 10^9

Algorithm

The basic idea of ​​binary search is to divide n elements into two roughly equal parts, and compare a[n/2] with x.

• If x=a[n/2], then find x and the algorithm stops;
• if x<a[n/2], as long as you continue to search for x in the left half of array a,
• if x>a[n/2], then as long as you search for x in the right half of array a.

Code

Java

• Java
• C++
• Python

• 
  public class Fixed_Point {
  
      // binary search, logN
      class Solution {
          public int fixedPoint(int[] A) {
              //Run binary search
              int lo = 0;
              int hi = A.length - 1;
  
              while (lo <= hi){
                  int mi = lo + (hi - lo) / 2;
                  if (A[mi] == mi) return mi;
                  if (mi < A[mi]) hi = mi - 1;
                  else lo = mi+1;
              }
  
              return -1;
          }
      }
  
  
      class Solution_bruteForce {
          public int fixedPoint(int[] A) {
              for (int i = 0; i < A.length; i++) {
                  if (A[i] == i) {
                      return i;
                  }
              }
              return -1;
          }
      }
  
  }
  
  

• // OJ: https://leetcode.com/problems/fixed-point/
  // Time: O(logN)
  // Space: O(1)
  class Solution {
  public:
      int fixedPoint(vector<int>& A) {
          int N = A.size(), L = 0, R = N - 1;
          while (L <= R) {
              int M = (L + R) / 2;
              if (A[M] < M) L = M + 1;
              else R = M - 1;
          }
          return L < N && A[L] == L ? L : -1;
      }
  };
  

• print("Todo!")
  

All Problems

All Solutions