이분법 검색

이분법은 매우 기본적인 알고리즘 사고이며, 어려움은 주로 경계의 제어, 즉 카드 형제 [왼쪽, 오른쪽]과 [왼쪽, 오른쪽]의 두 가지 아이디어의 차이에 있습니다. 처음으로 자신의 시간을 쓸 때도이 문제를 무시하고 오른쪽 = len (nums)-1을 사용하면 제출 프로세스에서 nums 1의 길이가 검색 조건을 직접 건너 뛰고 오류를보고하는 것으로 나타났습니다. 결국 수정되었습니다:

열린 간격 쓰기

 def search(self, nums: List[int], target: int) -> int:
 left = 0
 right = len(nums)
 while left < right:
 mid = left + (right - left)//2 #여기 중간= (left + right)//2  
 if nums[mid] > target:
 right = mid
 elif nums[mid] < target:
 left = mid + 1
 else:
 return mid
 return -1

닫힌 간격 쓰기

def search(self, nums: List[int], target: int) -> int:
 left = 0
 right = len(nums)-1
 while left <= right:
 mid = left + (right - left)//2
 if nums[mid] > target:
 right = mid-1
 elif nums[mid] < target:
 left = mid + 1
 else:
 return mid
 return -1

제목 링크:Binary Search

제목 링크:

34. 정렬된 배열에서 요소의 첫 번째와 마지막 위치 찾기

이분법으로 왼쪽과 오른쪽 경계를 각각 구합니다.

35. 삽입 위치 검색

차이점은 목표 값을 찾을 수 없는 경우 반환되는 값에 있습니다.

요소 제거하기

확장 문제 34, 35

폭력적인 솔루션

폭력적인 솔루션은 두 번, 한 번은 중복 값을 찾기 위해 한 번은 값을 삭제하기 위해 중복 값을 삭제하는 것을 잊지 않고 목록의 모든 요소의 중복 값을 삭제하는 것을 잊지 않으므로 이때 i의 위치는 아직 값을 찾지 못하고 i -= 1이 값을 건너 뛰지 않도록 보장합니다.

 def removeElement(self, nums: List[int], val: int) -> int:
 l = k = len(nums)
 i = 0
 while i < l:
 if nums[i] == val:
 k-=1
 for j in range(i,l-1):
 nums[j] = nums[j+1]
 i-=1
 l-=1
 i+=1
 return k

듀얼 포인터

 def removeElement(self, nums: List[int], val: int) -> int:
 slow = fast = 0
 while fast < len(nums):
 if nums[fast] == val:
 fast += 1
 else:
 nums[slow] = nums[fast]
 fast += 1
 slow += 1
 return slow