https://leetcode.com/problems/binary-search/description/
Binary Search - LeetCode
Can you solve this real interview question? Binary Search - 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.
leetcode.com
문제설명:
정렬된 리스트를 입력받아 이진검색으로 target에 해당하는 인덱스를 구하는 문제
이진탐색, 재귀로 구현
- mid 값은 지정해준다.
- 리스트의 중간값이 타겟과 같으면 반환해준다.
- 리스트의 중간값이 타겟보다 작으면
- left -> mid+1로 바꿔 재귀
- 리스트의 중간값이 타겟보다 크면
- right -> mid-1로 바꿔 재귀
idx = 0
def bs(lst, target, start, end):
nonlocal idx
if start == end:
idx = -1
return idx
mid = (start + end) // 2
if lst[mid] == target:
idx = mid
return idx
else:
if lst[mid] < target:
bs(lst, target, mid+1, end)
else:
bs(lst, target, start, mid)
return idx
result = bs(nums, target, 0, len(nums))
return result
'코딩테스트 > LeetCode' 카테고리의 다른 글
| [Python][LeetCode] Intersection of Two Arrays(두 배열의 교집합) (0) | 2023.11.01 |
|---|---|
| [Python][LeetCode] Search in Rotated Sorted Array(회전 정렬된 배열 검색) (0) | 2023.11.01 |
| [Python][LeetCode] Two Sum II (두 수의 합) (0) | 2023.11.01 |
| [Python][LeetCode] Search a 2D Matrix II(2D 매트릭스 검색) (0) | 2023.11.01 |
| [Python][leetCode] List Sort(리스트 정렬) (0) | 2023.10.30 |
