728x90
이진탐색은 정렬된 배열에서 특정한 값을 찾는 알고리즘이다
배열의 중간값을 기준으로 값을 찾고
찾고자하는 값과 중간값을 비교하고 탐색범위를 반으로 줄인다
탐색범위가 없을 때까지 반복한다
chatqpt에거 물어본 이진탐색
def binary_search(arr, target): #정렬, 찾고자 하는 값이 인수로 들어감
left = 0 #arr의 맨왼쪽인덱스
right = len(arr) - 1 #arr의 맨오른쪽인덱스
while left <= right: #비교했을 때 오른쪽이 작을때까지 반복 (즉 탐색할 배열이 없을때까지)
mid = (left + right) // 2
if arr[mid] == target: #가운데데 인덱스의 값이 찾고자하는 값이면
return mid #가운데인덱스를 리턴
elif arr[mid] < target: #찾고자하는 값보다 가운데 인덱스의 값이 작으면
left = mid + 1 #맨왼쪽, 첫번째 인덱스가 중간값부터 시작됨 (시작점을 바꿔서 기존 정렬을 반으로나누는것 뜻)
else:
right = mid - 1 #맨오른쪽, 마지막 인덱스가 중간값부터 시작됨(시작점을 바꿔서 기존 정렬을 반으로나누는것 뜻
return -1 #값을 못찾으면 -1 내보냄 너가 찾는 값없어~~이진 탐색은 검색, 정렬, 최솟값/최댓값 찾기 등 다양한 문제에서 사용됩니다.
이진 탐색은 탐색할 배열이 정렬되어 있어야 한다는 조건이 있지만, 이 조건을 만족한다면 빠른 탐색을 수행할 수 있는 알고리즘입니다. 이진 탐색은 효율적인 탐색을 위해 항상 고려해야 할 알고리즘 중 하나입니다.
728x90