이진탐색 binary search

이진탐색은 주어진 자료구조에서 원하는 항목을 빠르게 찾는 알고리즘 중 하나이며 정렬된 배열 또는 리스트에서 사용한다.

1. 배열이나 리스트를 정렬
2. 찾고자 하는 항목과 배열 또는 리스트의 중간 항목을 비교
3. 찾고자 하는 항목이 중간 항목보다 작으면, 중간 항목의 왼쪽 부분을 대상으로 이진탐색을 재귀적으로 수행
4. 찾고자 하는 항목이 중간 항목보다 크면, 중간 항목의 오른쪽 부분을 대상으로 이진탐색을 재귀적으로 수행
5. 찾고자 하는 항목을 찾을 때까지 이 과정을 반복

이진 탐색은 자료구조의 크기에 관계없이 시간 복잡도가 O(log n)이며 이진탐색의 효율성은 자료구조를 효율적으로 관리하고 검색을 수행하는 데 매우 유용하다.

 

 

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    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

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    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

# 사용자로부터 배열과 찾고자 하는 값을 입력 받음
arr = list(map(int, input("정렬된 배열을 입력하세요 (공백으로 구분): ").split()))
target = int(input("찾고자 하는 값을 입력하세요: "))

# 이진 탐색 함수 호출
result = binary_search(arr, target)

# 결과 출력
if result != -1:
    print(f"찾고자 하는 값 {target}은(는) 배열의 인덱스 {result}에 있습니다.")
else:
    print(f"배열에서 {target}을(를) 찾을 수 없습니다.")

정렬 후 출력

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    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

# 사용자로부터 배열과 찾고자 하는 값을 입력 받음
arr_input = input("정렬되지 않은 배열을 입력하세요 (공백으로 구분): ")
arr = list(map(int, arr_input.split()))
target = int(input("찾고자 하는 값을 입력하세요: "))

# 배열을 정렬
arr.sort()

# 정렬된 배열 출력
print("정렬된 배열:", arr)

# 이진 탐색 함수 호출
result = binary_search(arr, target)

# 결과 출력
if result != -1:
    print(f"찾고자 하는 값 {target}은(는) 배열의 인덱스 {result}에 있습니다.")
else:
    print(f"배열에서 {target}을(를) 찾을 수 없습니다.")

 

 

 

data structures and binary search are closely related. Binary search is one of the algorithms used to quickly find a desired item in a given data structure. Typically, it's used on sorted arrays or lists.

 

Binary search operates with the follwing steps

1. Sort the array or list

2. Compare the desired item with the middle item of the array or list.

3. If the desired item is smaller than the middle item, recursively perform binary search on the left part of the arrary or list. and If the desired item is lager than the middle item, recursively perform binary search on the right part of the array of list.

4. Repeat these steps until the desired item is found.

 

Binary serach is a highly efficient search algorithm, with a time complexity of O(log n), regardless of the size of the data structure. This efficiency makes binary search invaluable for efficiently managing and searching through data structures.