반응형
704. Binary Search
Easy
Given an array of integers nums
which is sorted in ascending order, and an integer target
, write a function to search target
in nums
. If target
exists, then return its index. Otherwise, return -1
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Constraints:
1 <= nums.length <= 104
-104 < nums[i], target < 104
- All the integers in
nums
are unique. nums
is sorted in ascending order.
나의 코드
class Solution:
def search(self, nums: List[int], target: int) -> int:
high, low = len(nums) - 1, 0
while low <= high:
mid = (high + low) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
이건 유명한 BS 템플릿이니까 외우도록 하자
728x90
반응형
'알고리즘 > LeetCode_Grind75' 카테고리의 다른 글
Grind75 - 21. Merge Two Sorted Lists 파이썬 (0) | 2024.11.28 |
---|---|
Grind75 - 121. Best Time to Buy and Sell Stock 파이썬 (0) | 2024.11.19 |
Grind75 - 242. Valid Anagram 파이썬 (0) | 2024.11.13 |
Grind75 - 125. Valid Palindrome 파이썬 (3) | 2024.11.04 |
Grind75 - 20. Valid Parentheses 파이썬 (0) | 2024.10.27 |