이분탐색

이분 탐색의 조건

원소가 정렬되어 있는 상태여야 한다.

중복되는 원소가 있는 이분 탐색

1. lower bound : 찾고자하는 값보다 크거나 같은 값이 처음 나오는 인덱스

def lowerBound(data, target):
	low = 0
   	high = data.length-1
    mid = (low + high) // 2
    
    while low < high: # 같다고 두면 while문을 빠져나갈 수 없다.
        if target <= data[mid]:
        	high = mid
        else:
        	low = mid + 1
        mid = (low + high) // 2
            
    return low # low == data.legnth-1 이면 taget이 모든 원소보다 값이 큰지 체크해야한다.

2. upper bound : 찾고자하는 값보다 큰 값이 처음 나오는 인덱스

def upperBound(data, target): # 같다고 두면 while문을 빠져나갈 수 없다.
	low = 0
   	high = data.length-1
    mid = (low + high) // 2
    
    while low < high:
        if target >= data[mid]:
        	low = mid + 1
        else:
        	high = mid
        mid = (low + high) // 2
            
    return low

중복되는 원소가 없는 이분 탐색

일반적인 이분 탐색과 같다.

def binarySearch(data, target):
	low = 0
   	high = data.length-1
    mid = (low + high) // 2
    
    while low <= high:
        if target < data[mid]:
        	low = mid + 1
        elif target > data[mid]:
        	high = mid - 1
        else:
        	return mid
     	mid = (low + high) // 2
            
    return -1 # 원하는 원소를 못 찾은 경우