Description
有一个有序数组arr,其中不含有重复元素,请找到满足arr[i]==i条件的最左的位置。如果所有位置上的数都不满足条件,返回-1。
给定有序数组arr及它的大小n,请返回所求值。
测试样例:
[-1,0,2,3],4
返回:2
Solutions
1. Binary Search
# -*- 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