Как найти ближайшее число в массиве python

Given an array of sorted integers. We need to find the closest value to the given number. Array may contain duplicate values and negative numbers. 

Examples:  

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

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

A simple solution is to traverse through the given array and keep track of absolute difference of current element with every element. Finally return the element that has minimum absolution difference.

Method #1: Using Binary search

Python3

def findClosest(arr, n, target):

    if (target <= arr[0]):

        return arr[0]

    if (target >= arr[n - 1]):

        return arr[n - 1]

    i = 0

    j = n

    mid = 0

    while (i < j):

        mid = (i + j) // 2

        if (arr[mid] == target):

            return arr[mid]

        if (target < arr[mid]):

            if (mid > 0 and target > arr[mid - 1]):

                return getClosest(arr[mid - 1], arr[mid], target)

            j = mid

        else:

            if (mid < n - 1 and target < arr[mid + 1]):

                return getClosest(arr[mid], arr[mid + 1], target)

            i = mid + 1

    return arr[mid]

def getClosest(val1, val2, target):

    if (target - val1 >= val2 - target):

        return val2

    else:

        return val1

arr = [1, 2, 4, 5, 6, 6, 8, 9]

n = len(arr)

target = 11

print(findClosest(arr, n, target))

Time Complexity: O(log(n))
Auxiliary Space: O(log(n)) (implicit stack is created due to recursion)

Method #2: Using min() function

Python3

def findClosestValue(givenList, target):

    def difference(givenList):

        return abs(givenList - target)

    result = min(givenList, key=difference)

    return result

if __name__ == "__main__":

    givenList = [1, 2, 4, 5, 6, 6, 8, 9]

    target = 11

    result = findClosestValue(givenList, target)

    print("The closest value to the " + str(target)+" is", result)

Output

The closest value to the 11 is 9

Method #3: Using Two Pointers

Another approach to solve this problem is to use two pointers technique, where we maintain two pointers left and right, and move them towards each other based on their absolute difference with target.

Below are the steps:

  1. Initialize left = 0 and right = n-1, where n is the size of the array.
  2. Loop while left < right
    • If the absolute difference between arr[left] and target is less than or equal to the absolute difference between arr[right] and target, move left pointer one step to the right, i.e. left++
    • Else, move right pointer one step to the left, i.e. right–-
  3. Return arr[left], which will be the element closest to the target.

Below is the implementation of the above approach:

Python3

import sys

def findClosest(arr, n, target):

    left, right = 0, n - 1

    while left < right:

        if abs(arr[left] - target) <= abs(arr[right] - target):

            right -= 1

        else:

            left += 1

    return arr[left]

if __name__ == "__main__":

    arr = [1, 2, 4, 5, 6, 6, 8, 8, 9]

    n = len(arr)

    target = 11

    print(findClosest(arr, n, target))

Time Complexity: O(N), where n is the length of the array.
Auxiliary Space: O(1)

Please refer complete article on Find closest number in array for more details!
 

Last Updated :
17 Apr, 2023

Like Article

Save Article

Источник

Для неотсортированного массива. Для отсортированного лучше использовать бинпоиск.

Python 3.4+: tio.run

def f(a, val):
  return min((x for x in a if x > val), default=None)

a = [1, 2, 5, 22, 33, 44, 312]
print(f(a, 3))
print(f(a, 10))
print(f(a, 1000))

Более ранние версии: tio.run

def f(a, val):
  return min([x for x in a if x > val] or [None])

a = [1, 2, 5, 22, 33, 44, 312]
print(f(a, 3))
print(f(a, 10))
print(f(a, 1000))

Вывод в обоих случаях:

5
22
None

Источник

Numpy is a library for scientific computing in Python, and it provides several functions to find the nearest value and its index in an array:

Table of contents

  • Using argmin() function
  • Other example with multidimensional array
    • Example 1
    • Example 2
  • References

Using argmin() function

One of the most commonly used methods is using numpy’s argmin() function. This allows us to search through an entire array to find the closest number (or value) and its corresponding index. For example, say we have an array of numbers: 

import numpy as np

A = np.random.random(10)

This code generate for example

array([ 0.47009242,  0.40242778,  0.02064198,  0.47456175,  0.83500227,
        0.53205104,  0.14001715,  0.86691798,  0.78473226,  0.91123132])

We can use numpy’s argmin() function to find the index of the closest value of

value = 0.5

idx = (np.abs(A-value)).argmin()

in this case it would be 

3

Note that:

A[idx]

gives

0.47456175235592957

Other example with multidimensional array

Example 1

In the case of a multidimensional array: 

>>> A = np.random.random((4,4))
>>> A
array([[ 0.81497314,  0.63329046,  0.53912919,  0.19661354],
       [ 0.71825277,  0.61201976,  0.0530397 ,  0.39322394],
       [ 0.41617287,  0.00585574,  0.26575708,  0.39457519],
       [ 0.25185766,  0.06262629,  0.69224089,  0.89490705]])
>>> X = np.abs(A-value)
>>> idx = np.where( X == X.min() )
>>> idx
(array([0]), array([2]))
>>> A[idx[0], idx[1]]
array([ 0.53912919])
>>>

Example 2

>>> value = [0.2, 0.5]
>>> A = np.random.random((4,4))
>>> A
array([[ 0.36520505,  0.91383364,  0.36619464,  0.14109792],
       [ 0.19189167,  0.10502695,  0.39406069,  0.04107304],
       [ 0.96210652,  0.5862801 ,  0.12737704,  0.33649882],
       [ 0.91871859,  0.95923748,  0.4919818 ,  0.72398577]])
>>> B = np.random.random((4,4))
>>> B
array([[ 0.61142891,  0.90416306,  0.07284985,  0.86829844],
       [ 0.2605821 ,  0.48856753,  0.55040045,  0.65854238],
       [ 0.83943169,  0.64682588,  0.50336359,  0.90680018],
       [ 0.82432453,  0.10485762,  0.6753372 ,  0.77484694]])
>>> X = np.sqrt( np.square( A - value[0] ) +  np.square( B - value[1] ) )
>>> idx = np.where( X == X.min() )
>>> idx
(array([2]), array([2]))
>>> A[idx[0], idx[1]]
array([ 0.12737704])
>>> B[idx[0], idx[1]]
array([ 0.50336359])

References

Источник

Студворк — интернет-сервис помощи студентам

Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.

Входные данные

В первой строке содержатся список чисел — элементы массива (целые числа, не превосходящие 1000

по абсолютному значению).

Во второй строке вводится одно целое число x
, не превосходящее 1000

по абсолютному значению.

Выходные данные

Вывести значение элемента массива, ближайшего к x
. Если таких чисел несколько, выведите любое из них.

Python 
1
2
3
4
5
6
7
8
9
10
11

a, n, find_num = [int(i) for i in input().split()], int(input()), 100
for i in range(len(a)):
    if a[i] < n:
        find_num = -find_num
    else:
        find_num = find_num + 0
    if a[i] >= n and a[i] - n <= find_num - n:
        find_num = a[i]
    elif a[i] <= n and find_num - n <= a[i] - n:
        find_num = a[i]
print(find_num)
Источник

Задача: Найдите ближайшее значение к переданному.

Вам даны список значений в виде множества (Set) и значение, относительно которого, надо найти ближайшее.
Несколько уточнений:

Если 2 числа находятся на одинаковом расстоянии — необходимо выбрать наименьшее из них;
Ряд чисел всегда не пустой, т.е. размер >= 1;
Переданное значение может быть в этом ряде, а значит оно и является ответом;
В ряде могут быть как положительные, так и отрицательные числа, но они всегда целые;
Ряд не отсортирован и состоит из уникальных чисел.

Решение предлагают такое:

def nearest_value(values: set, one: int) -> int:
    return min(values, key=lambda n: (abs(one - n), n))

Как работает часть (abs(one — n), n)?

Источник

Понравилась статья? Поделить с друзьями:
  • Как найти ооо на сайте ифнс
  • Как лайтрум найдет файлы
  • Как найти больше кандидатов
  • Как найти крупного инвестора для бизнеса
  • Нарушение аппаратной конфигурации secret net как исправить