# My accepted O(2 * log(n)) solution, use the

• Use the answer of the "searchInsert" problem.

The searchInsert function return the insert position of the target.

If target in array, the range's left index is target's insert position, and range's right index is (target + 1)'s insert position - 1.

``````class Solution:
# @param A, a list of integers
# @param target, an integer to be searched
# @return a list of length 2, [index1, index2]
def searchRange(self, A, target):
if type(A) != list:
raise TypeError

if A == []:
return [-1, -1]

a = self.searchInsert(A, target)
if A[a] == target:
return [a, self.searchInsert(A, target + 1) - 1]
else:
return [-1, -1]

# @param A, a list of integers
# @param target, an integer to be inserted
# @return integer(target's insert position)
def searchInsert(self, A, target):
if type(A) != list:
raise TypeError

if A == []:
return 0

a, b = 0, len(A) - 1

while a < b:
c = a + ((b - a) >> 1)
if target <= A[c]:
if c == 0 or target > A[c - 1]:
return c
b = c
else:
if c == len(A) - 1 or target <= A[c + 1]:
return c + 1
a = c + 1

if target <= A[a]:
return a
else:
return a + 1``````

• The problem requires O(logn), is O(log(n^2)) also ok?

• I think it's ok. Anyway, 2 is just a constant value.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.