Description

有一个有序数组arr，其中不含有重复元素，请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件，返回-1。

给定有序数组arr及它的大小n，请返回所求值。

测试样例：

[-1,0,2,3],4
返回：2

Solutions

# -*- coding:utf-8 -*-
# Time: O(n)
# Space: O(1)
class Find:
    def findPos(self, nums, n):
        # write code here
        if not nums or nums[0] > n -1 or nums[n-1] < 0:
            return -1
        res = -1
        l, r = 0, n-1
        while l <= r:
            mid = l + ((r - l) >> 1)
            if nums[mid] == mid:
                res = mid
                r = mid - 1
            elif nums[mid] < mid:
                l = mid + 1
            else:
                r = mid - 1
        return res

References

  1. 6.6 最左原位