class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return -1
풀이를 보면, 중간 값을 구하는 다른 방법을 확인할 수 있습니다.
각 방식에 대해서 ChatGPT에게 물어보면,
- (l + r) // 2
- 이 방법은 두 수의 합을 구한 후에 2로 나눈 후 소수점을 버립니다. (내림)
- 이 방법은 가장 간단하지만, 중간 값이 매우 큰 경우에는 오버플로우가 발생할 수 있습니다.
-
- 이 방법은 두 수의 차를 구한 후에 2로 나눈 후 소수점을 버립니다. (내림)
- 그 결과를 l 에 더하여 중간 값을 찾습니다.
- 이 방법은 오버플로우의 위험이 적으며, 좀 더 안전한 방법입니다.l + {(r - l) // 2}
- l + r >>> 1
- 이 방법은 두 수의 합을 구한 후 비트 연산자인 >>>를 사용하여 오른쪽으로 1 비트 이동시킵니다.
- 이 방법은 오버플로우의 위험이 없으며, 또한 매우 효율적입니다.
- 그러나 이해하기 어려울 수 있습니다.
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
l, r = 0, len(nums)-1
while l <= r:
mid = l + ((r-l)//2)
if nums[mid] == target:
return mid
if nums[mid] < target:
l = mid + 1
else:
r = mid - 1
return -1
- 두 번째 방법으로 다시 풀어보면, 테스트 예제의 차이가 있어서 그런지 큰 차이를 보이지는 않습니다.
'LeetCode' 카테고리의 다른 글
169, Majority Element (0) | 2024.05.23 |
---|---|
235, Lowest Common Ancestor of a Binary Search Tree (0) | 2024.02.25 |
217, Contains Duplicate (0) | 2024.02.19 |