이진탐색

• 특정 기준으로 정렬된 배열에서 범위를 반씩 줄여가며 원하는 숫자(target)을 찾는 알고리즘

def binary_search(numbers, key):
    left = 0
    right = len(numbers)-1
  
    while left <= right:
    	#범위를 반씩 줄이기
        mid = (left + right) // 2
        #원하던 숫자를 찾음
        if key == numbers[mid]:
            return numbers[mid]
        elif key < numbers[mid]:
        	#right는 항상 key보다 작거나 같음을 보장
            right = mid - 1
        elif key > numbers[mid]:
        	#left는 항상 key보다 크거나 같음을 보장
            left = mid + 1
    # right가 left보다 왼쪽으로 간다면 찾지 못한 케이스
    return -1

이분탐색의 찾는 key가 없는 경우

• 위처럼 일반적인 이진탐색으로 찾는다면 찾는 수가 없을 경우 -1 return된다.이때 아래처럼 3가지의 케이스로 나뉜다.
  • 찾는 수가 리스트의 모든 수보다 작을 때 (left:0,right:-1)
  • 찾는 수가 리스트의 모든 수보다 클 때 (left:last index of list+1,right:last index of list)
  • 찾는 수가 리스트의 가장 작은 수와 가장 큰 수 사이에 있을 때(left: bigger than key with nearest num index,right:smaller than key with nearest num index)

이분탐색으로 가장 가까운 수 찾기

def binary_search(numbers, key):
    left = 0
    right = len(numbers)-1
    while left <= right:
        mid = (left + right) // 2
        if key == numbers[mid]:
            return numbers[mid]
        elif key < numbers[mid]:
            right = mid - 1
        elif key > numbers[mid]:
            left = mid + 1
    #특정 수를 찾지 못한 3가지 경우를 처리
    if right == -1:
    	#찾는 수가 리스트보다 작은 경우 리스트의 가장 작은 수 반환
        return numbers[0]
    elif left == len(numbers):
    	#찾는 수가 리스트보다 큰 경우 리스트의 가장 큰 수 반환
        return numbers[-1]
    else:
    	#찾는 수가 리스트사이에 있을 때 찾는수보다 크면서 가장 가까운수,작으면서 가장 가까운수를 비교
        right_number = numbers[left]
        left_number = numbers[right]
            
        right_abs = abs(key - right_number)
        left_abs = abs(key - left_number)
      
        if right_abs == left_abs:
        	# 두 수의 간격이 모두 같다면 오른쪽값(아무값이나 상관없음)반환
            return right_number
        elif right_abs > left_abs: # next is closer
        	# 작으면서 가장 가까운 수의 간격이 더 좁다면 작으면서 가장 가까운 수 반환
            return left_number
        elif right_abs < left_abs:
        	# 크면서 가장 가까운 수의 간격이 더 좁다면 크면서 가장 가까운 수 반환
            return right_number

=============key가 리스트중에 있는 경우==============
list: [10, 20, 30, 40], key: 20, nearest key: 20
=============key가 리스트의 가장 작은 수보다 작은 경우==============
list: [10, 20, 30, 40], key: 5, nearest key: 10
=============key가 리스트의 가장 큰 수보다 큰 경우==============
list: [10, 20, 30, 40], key: 45, nearest key: 40
=============key가 리스트의 가장 작은 수와 가장 큰 수 사이에 있을 경우==============
list: [10, 20, 30, 40], key: 33, nearest key: 30

위도 경도 2차원 배열의 이분탐색(key가 존재할 때)

• 지금까지의 이분탐색은 특정 기준으로 정렬된 1차원 배열에서 단순히 좌우 범위를 반씩 줄여 탐색해나갔다.

• 특정 기준은 지도의 위도,경도 데이터를 기반으로 정렬한다.

• 찾고자하는 key가 항상 list에 존재할 경우를 전제하고 로직을 구성

def lat_lon_array_binary_search(coordi__gps_list,key):
    # print("==========",key)

    #x=>행(위도)
    #y=>열(경도)
    last_column=len(coordi__gps_list[0])-1
    last_row=len(coordi__gps_list)-1

    x_up=0
    x_down=len(coordi__gps_list)-1
    y_left=0
    y_right=last_column
    # 찾는 key가 무조건 존재한다는 가정하에 조건을 분기
    while( x_up<=x_down and y_left<=y_right):
        x_mid=(x_up+x_down)//2
        y_mid=(y_left+y_right)//2
        cur_key=coordi__gps_list[x_mid][y_mid]
        # print(f"x_up: {x_up} , x_down: {x_down}, y_left: {y_left} , y_right: {y_right}")
        # print(x_mid,y_mid)
        if key==cur_key:
            # 찾는 값과 일치한다면 바로 반환
            return (x_mid,y_mid)
        
        elif key[0]==cur_key[0]:
            # 위도가 같다면 위도의 범위를 한개로 좁힘
            x_up=x_mid
            x_down=x_mid

            if key[1]<cur_key[1]:
                # 경도가 더 작다면 경도의 범위를 왼쪽으로 좁힘
                y_right=y_mid-1

            elif key[1]>cur_key[1]:
                # 경도가 더 크다면 경도의 범위를 오른쪽으로 좁힘
                y_left=y_mid+1

        elif key[0]<cur_key[0]:
            # 위도가 더 작다면 위도의 범위를 아래로 좁힘 
            x_up=x_mid+1

            if key[1]>cur_key[1]:
                # 경도가 더 크다면 경도의 범위를 오른쪽으로 좁힘
                y_left=y_mid+1
            elif key[1]==cur_key[1]:
                # 경도가 같았다면 경도의 범위를 기준포함 오른쪽으로 좁힘
                y_left=y_mid

        elif key[0]>cur_key[0]:
            # 위도가 더 크다면 위도의 범위를 위로 좁힘
            x_down=x_mid-1
        
            if key[1]<cur_key[1]:
                # 경도가 더 작다면 경도의 범위를 왼쪽으로 좁힘
                y_right=y_mid-1
            elif key[1]==cur_key[1]:
                # 경도가 같다면 경도의 범위를 기준 포함 왼쪽으로 좁힘
                y_right=y_mid
	return -1

실제 지도에서의 매핑좌표

• 좌표정보들을 실제 경도,위도상에 매핑하면 평행사변형의 형태를 뛴다.

• 이를 이용한다면 영역별로 나누고 기하학적 분석을 통해 범위를 벗어날 때와 벗어나지 않을 때 가장 가까운 경도,위도의 좌표데이터를 매핑할 수 있다.

가장 가까운 위도,경도 찾기

• 위도를 중심으로 이진탐색을 했으므로 위도를 기준으로 영역을 3가지로 나눈다.

최종코드

def lat_lon_array_binary_search(coordi__gps_list,key):
    # print("==========",key)

    #x=>행(위도)
    #y=>열(경도)
    last_column=len(coordi__gps_list[0])-1
    last_row=len(coordi__gps_list)-1

    x_up=0
    x_down=len(coordi__gps_list)-1
    y_left=0
    y_right=last_column
    # 찾는 key가 무조건 존재한다는 가정하에 조건을 분기
    while( x_up<=x_down and y_left<=y_right):
        x_mid=(x_up+x_down)//2
        y_mid=(y_left+y_right)//2
        cur_key=coordi__gps_list[x_mid][y_mid]
        # print(f"x_up: {x_up} , x_down: {x_down}, y_left: {y_left} , y_right: {y_right}")
        # print(x_mid,y_mid)
        if key==cur_key:
            # 찾는 값과 일치한다면 바로 반환
            return (x_mid,y_mid)
        
        elif key[0]==cur_key[0]:
            # 위도가 같다면 위도의 범위를 한개로 좁힘
            x_up=x_mid
            x_down=x_mid

            if key[1]<cur_key[1]:
                # 경도가 더 작다면 경도의 범위를 왼쪽으로 좁힘
                y_right=y_mid-1

            elif key[1]>cur_key[1]:
                # 경도가 더 크다면 경도의 범위를 오른쪽으로 좁힘
                y_left=y_mid+1

        elif key[0]<cur_key[0]:
            # 위도가 더 작다면 위도의 범위를 아래로 좁힘 
            x_up=x_mid+1

            if key[1]>cur_key[1]:
                # 경도가 더 크다면 경도의 범위를 오른쪽으로 좁힘
                y_left=y_mid+1
            elif key[1]==cur_key[1]:
                # 경도가 같았다면 경도의 범위를 기준포함 오른쪽으로 좁힘
                y_left=y_mid

        elif key[0]>cur_key[0]:
            # 위도가 더 크다면 위도의 범위를 위로 좁힘
            x_down=x_mid-1
        
            if key[1]<cur_key[1]:
                # 경도가 더 작다면 경도의 범위를 왼쪽으로 좁힘
                y_right=y_mid-1
            elif key[1]==cur_key[1]:
                # 경도가 같다면 경도의 범위를 기준 포함 왼쪽으로 좁힘
                y_right=y_mid
    print(x_up,x_down,y_left,y_right)
    if x_up==x_down: 
        #특정 위도가 잡혔을 경우-
        min_y=coordi__gps_list[x_up][0][1]
        max_y=coordi__gps_list[x_up][last_column][1]
        if min_y<=key[1]<=max_y:
            return (x_up,binary_search(coordi__gps_list[x_up],key,1))
        elif key[1]<min_y:
            #완탐 범위를 아래로
            return linear_search(coordi__gps_list,key,start=x_up) 
        elif max_y<key[1]:
            #완탐 범위를 위로
            return linear_search(coordi__gps_list,key,end=x_down)
    elif x_up!=len(coordi__gps_list[0]) and x_down!=-1:
        #특정 위도가 잡히진 않았지만 사이위도일 경우
        min_y=min(coordi__gps_list[x_up][0][1],coordi__gps_list[x_down][0][1])
        max_y=max(coordi__gps_list[x_up][last_column][1],coordi__gps_list[x_down][last_column][1])

        if min_y<=key[1]<=max_y:
            x_up_y=binary_search(coordi__gps_list[x_up],key,1)
            x_down_y=binary_search(coordi__gps_list[x_down],key,1)
            if math.dist(key,coordi__gps_list[x_up][x_up_y])<math.dist(key,coordi__gps_list[x_down][x_down_y]):
                return (x_up,x_up_y)
            else:
                return (x_down,x_down_y)
        elif key[1]<min_y:
            #완탐 범위를 아래로
            return linear_search(coordi__gps_list,key,start=x_down) 
        elif max_y<key[1]:
            #완탐 범위를 위로
            return linear_search(coordi__gps_list,key,end=x_up)
    elif x_down==-1:
        min_y=coordi__gps_list[0][0][1]
        max_y=coordi__gps_list[0][last_column][1]
        if min_y<=key[1]<=max_y:
            return (0,binary_search(coordi__gps_list[0],key,1))
        elif key[1]<min_y:
            return linear_search(coordi__gps_list,key) 
        elif max_y<key[1]:
            return (0,last_column)
    elif x_up==len(coordi__gps_list[0]):
        min_y=coordi__gps_list[last_row][0][1]
        max_y=coordi__gps_list[last_row][last_column][1]
        if min_y<=key[1]<=max_y:
            return (last_row,binary_search(coordi__gps_list[last_row],key,1))
        elif key[1]<min_y:
            return (last_row,0)
        elif max_y<key[1]:
            return linear_search(coordi__gps_list,key)
    return (-1,-1)