• 欢迎光临~

# 代码随想录刷题营day1｜704.二分查找 34. 有序数组找首位末位 35.搜索插入的位置 27.移除元素

• 数组下标都是从0开始的
• 数组内存空间的地址是连续的
• 数组的元素是不能删的，只能覆盖

```class Solution:
def search(self, nums: List[int], target: int) -> int:
# sorted array - BS 目的：缩小查找范围
# l, r
l=0
r=len(nums)
while l<r:
m = l + (r - l)//2
if nums[m] == target:
return m
elif nums[m]>target:
r = m
else:
l = m+1
return -1
```

non-decreasing order-BS，target

```class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
#non-decreasing order-BS，target，lower bound & upper bound
#O(log n) ---- 100% BS solution

''''while l<r:
if nums[m]>target:
r=m
if nums[m]<target:
l=m+1
if nums[m]==target:
l+=1
r-=1
#这道题的难点在于：如何确定下边界和上边界，怎么缩小范围
return [-1,-1]'''
def search(x):
l, r = 0, len(nums)
while l < r:
m = l+(r-l) // 2
if nums[m] < x: #这里严格小于缩小范围会得到下边界，同理严格大于缩小范围的思路会得到上边界。很tricky的一个细节，要注意！
l = m+1
else:
r = m
return l

l = search(target)
r = search(target+1)-1

if l <= r:
return [l, r]

return [-1, -1]
'''
[5,7,7,7,7,8,8,8,10] target=8
l=search(8)
r=search(9)-1
search(x)
l=0,5,
r=9,9,
m=4,7,
nums[m]=7<8
nums[m]=8
expect output[5,7]
'''```

debug:　　IndentationError: unexpected indent  缩进不对

sorted array+target需要缩小范围搜索，用二分查找

```class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l=0
r=len(nums)
while l<r:
m=l+(r-l)//2
if nums[m]<target:
l=m+1else:
r=m
return l```

https://leetcode.com/problems/remove-element/

```class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
p=0
for i in range(len(nums)):
if nums[i]==val:
continue
nums[p]=nums[i]
p+=1
return p```