Binary Search in Python: Find Closest Number

In this video, we will be given a sorted array and a target number. Our goal is to find a number in the array that is closest to the target number. We will be making use of binary search to solve this problem.

The array may contain duplicate values and negative numbers.

Example 1:
Input : arr[] = {1, 2, 4, 5, 6, 6, 8, 9}
Target number = 11
Output : 9
9 is closest to 11 in given array

Example 2:
Input :arr[] = {2, 5, 6, 7, 8, 8, 9};
Target number = 4
Output : 5

This video is one part of the Binary Search playlist on my channel. For more videos on binary search and how to apply it to various problems, check out the other videos:

The software written in this video is available at:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[Cloud-]

Thank you! This was very helpful. I'm self taught student so content like this is like a goldmine

[alexandraxu]

awesome explanation, you made it so clear each step, love your programming videos. Just one thing, the code doesn't work when there are two elements in the array. I just added another edge case, then it worked fine.
if len(array) == 2:
if abs(array[0]-target)> abs(array[1]-target):
return array[1]
else:
return array[0]

[samarthbhandari]

Hi great work on the videos, I have been following your videos for a few days now. I just wanted to point out one thing, when you calculate the midpoint it is better to calculate it as mid = low + (high-low)//2. This would prevent overflowing in case of extremely large inputs since if our low + high exceeds the maximum integer value it will calculate the midpoint wrong and is a very basic mistake a lot of people tend to overlook, especially from an interview perspective. Thanks for all these videos, please keep adding to these!

[maximpodkolzin]

either I'm doing something wrong or algorithm does not work for case when target number is not in the array and it's smaller than array's minimum, e.g [1, 2, 3, 4, 5, 6], target = -1

[namefunction]

This playlist is very helpful. Well explained and intriguing solution.

[KK--KK]

This is a great video. Really appreciate it.
#Just one question: if use array = [1, 2, 3, 4, 11, 14, 16, 17, 20] as an example and target value is 10, then mid is 11 and is closest to 10, but it will be skipped using your code, right? probably we need to include a line to compare A[mid]-target with the mid_diff_left and mid_diff_right.

[sudarshanhavale]

Your videos are very helpful to learn algorithms, keep it coming :)
Here is another version of the solution in which I tried to handle "get minimum difference value" differently (which works fine I guess), but I would appreciate it if you could review my code, and let me know whether it's worth skipping that "left and right difference" logic.

```
def find_closest_number_2(input_list, target):
min_diff = float('inf')
low = 0
high = len(input_list) - 1
closest_num = None

# Edge cases to handle empty lists
# and lists with single element.
if len(input_list) == 0:
return None
if len(input_list) == 1:
return input_list[0]

while low <= high:
mid = (low + high) // 2

# Get current difference and and store
# if its less than prior difference.
curr_diff = abs(input_list[mid] - target)
if curr_diff < min_diff:
min_diff = curr_diff
closest_num = input_list[mid]

# Move the mid point accordingly as it done
# via binary search
if input_list[mid] < target:
low = mid + 1
elif input_list[mid] > target:
high = mid - 1
else:
return input_list[mid]

return closest_num


A = [1, 2, 4, 5, 6, 6, 8, 9]
B = [2, 5, 6, 7, 8, 8, 9]

print (find_closest_number_2(A, 11))
# Result 9
print (find_closest_number_2(B, 4))
# Result 5
```

[asiradnan]

I tried your code and found from the array [1, 2, 6, 7, 8, 9], if the target is 0, it gives 2 as output whereas it should be 1, right?

[DoxxingWhoami]

Thanks for doing this exercise, I liked it, and if it continues like this

[captain_vegan]

Local variable 'min_diff_left' might be referenced before assignment

[dylanl]

I like watching your videos. For this question, why not just compare abs(A[mid] - target) with min_diff like below?


import sys


def find_closest_num(A, target):
min_diff = sys.maxsize
low = 0
high = len(A) - 1
closest_num = None

if len(A) == 0:
return None
if len(A) == 1:
return A[0]

while(low <= high):
mid = (low + high) // 2

if abs(A[mid] - target) < min_diff:
min_diff = abs(A[mid] - target)
closest_num = A[mid]

if A[mid] < target:
low = mid + 1
elif A[mid] > target:
high = mid - 1
else:
return A[mid]

return closest_num

[adrift]

in this code, if we input the array [1, -2, -8, 4, 5], the output is -2. if i print the mid, it is 2 and 3. why are there 2 values of mid? and if i debug this, it shows 2 as mid but works with mid as 3!!

[rajeshmanghani]

I think if you checked with the last item, you would have saved lot of time for eg. if target > A[len(A)-1]: return A[len(A)-1]

[anshulvairagade]

Sir, I didn't understand those if statements
If mid + 1 < Len(A):
And min > 0
Please help me !

[idan]

Are you checking A[mid+1] and A[mid-1] due to the division by two? (even number of elements)

[williamkwon]

could you explain what is the min_diff part? I am not sure why set that if min_diff_left < min diff because this will be always true since there is no number bigger than infinity. I am not sure what you try to check in this statement? is there case this condition is not true?

[elisad]

Hi, super helpful video! Question - I tried with this test case "a7 = [0, 3]
print(find_closest_num(a7, 1))" but got an error "UnboundLocalError: local variable 'min_diff_left' referenced before assignment".
So I think it's because the `if mid > 0' condition is skipped (since mid = 0), so 'mid_diff_left' is never assigned.
How can we fix it in this case? I'm thinking adding an 'else' statement somewhere but not sure how to... thank you!

[GopalaKrishnangk]

How about using iterative approach here?


def closes_number(l1, target):
diff = None
closest_no = None
for data in l1:
if target > data:
temp = target-data
elif target < data:
temp = data - target
else:
return data
if diff is None:
diff = temp
elif temp < diff:
diff = temp
closest_no = data
return closest_no

[vnpikachu]

Great works as always this lesson helped me solve two problem i had struggled recently. Could this method be applied to problem '' find subsequence of a sorted array has sum closest to a given value''?

[sanjaya]

sorry just a silly question if array = [2, 4, 6, 8, 10] and target value is 5 than abs(4-5)=1 and 6-5=1 does this program is intended to show only right value as in my case it always shows 6 as output.