Binary Search without trick of +/- 0.5, Python

• ``````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 not A:
return [-1,-1]

left=0
right=len(A)-1

def findR(left,right):
while True:

if left>right:
return -1
if left==right:
if A[left]==target:
return left
else:
return -1
mid=(left+right)//2

if A[mid]>target:
right=mid

elif A[mid]<target:
left=mid+1

else:
if mid+1<len(A) and A[mid+1]>target:
return mid
else:
left=mid+1

def findL(left,right):
while True:

if left>right:
return -1
if left==right:
if A[left]==target:
return left
else:
return -1
mid=(left+right)//2

if A[mid]>=target:
right=mid

elif A[mid]<target:
left=mid+1

while True:
if left>right:
return [-1,-1]
if left==right:
if A[left]==target:
return [left,right]
else:
return [-1,-1]

mid=(left+right)//2

if A[mid]<target:
left=mid+1
elif A[mid]>target:
right=mid
else:
if A[left]==target and A[right]==target:
return [left, right]
elif A[left]==target:
right=findR(mid,right)

elif A[right]==target:
left=findL(left,mid)

else:
right=findR(mid,right)
left=findL(left,mid)

return [left,right]
``````

It is kind of long.. But purely binary search

• Your code is too long, this is mine, short and clear

``````class Solution():
def searchRange(self, A, target):
res = [-1, -1]
l = 0
r = len(A) - 1
while l <= r:
m = l + (r - l) / 2
if A[m] == target:
res[0] = m
r = m - 1
elif A[m] < target:
l = m + 1
else:
r = m - 1
l = 0
r = len(A) - 1
while l <= r:
m = l + (r - l) / 2
if A[m] == target:
res[1] = m
l = m + 1
elif A[m] < target:
l = m + 1
else:
r = m - 1
return res``````

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