Binary search problem

algorithm
algorithm

1. Bianry Search for closest number problem

  • Input : ordred list of integers, a given number

  • Ouptut : find the the closest number to the given number

  • solution in python

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # recursion solution
    def solve(arr, num, start=0):
    	# 01. base case : size() <= 3
    	if len(arr) <= 3:
    		minVal = min([abs(x - num) for x in arr])
    		for i in range(len(arr)):
    			if minVal == abs(arr[i] - num):
    				return start + i
    	# 02. check the mid value then exclude the wrong side
    	mid = int(len(arr)/2)
    	if arr[mid] < num:
    		return solve(arr[mid + 1:], num, start + mid + 1)
    	else:
    		return solve(arr[:mid + 1], num, start)

  • solution in C++

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    // recursive solution
    int solve(vector<int> arr, int num, int start, int end){
    	// 01. base case : size() <= 3
    	if (end - start <= 2){
    		int min_val = abs(num - arr[start]);
    		for (int i=start; i <= end; i++)
    			min_val = min(abs(num - arr[i]), min_val);
    		for (int i=start; i <= end; i++)
    			if min_val == abs(num - arr[i])		
    				return i;
    	}
    	// 02. check the mid value then exclude the wrong side
    	int mid = (end - start)/2;
    	if (arr[mid] < num)
    		return solve(arr, num, mid + 1, end);
    	else
    		return solve(arr, num, start, mid);
    }
Share Comments