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 = -10, A = -5, A = 0, A = 3, thus the output is 3. Example 2: Input: [0,2,5,8,17] Output: 0 Explanation: A = 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
The basic idea of binary search is to divide n elements into two roughly equal parts, and compare
a[n/2] with x.
x=a[n/2], then find x and the algorithm stops;
x<a[n/2], as long as you continue to search for x in the left half of array a,
x>a[n/2], then as long as you search for x in the right half of array a.