Как найти ближайший элемент массива к заданному

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

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

Источник

Дан отсортированный массив целых чисел, найти k ближайшие элементы к target в массиве, где k а также target заданы положительные целые числа.

The target может присутствовать или отсутствовать во входном массиве. Если target меньше или равно первому элементу входного массива, вернуть первым k элементы. Точно так же, если target больше или равно последнему элементу входного массива, вернуть последний k элементы. Возвращаемые элементы должны быть в том же порядке, что и во входном массиве.

 
Например,

Input:  [10, 12, 15, 17, 18, 20, 25], k = 4, target = 16
Output: [12, 15, 17, 18]

 
Input:  [2, 3, 4, 5, 6, 7], k = 3, target = 1
Output: [2, 3, 4]

 
Input:  [2, 3, 4, 5, 6, 7], k = 2, target = 8
Output: [6, 7]

Потренируйтесь в этой проблеме

Идея состоит в том, чтобы выполнить линейный поиск, чтобы найти точку вставки. i. Точка вставки определяется как точка, в которой ключ target будет вставлен в массив, т. е. индекс первого элемента больше ключа, или размер массива, если все элементы в массиве меньше указанного ключа. Затем сравните элементы вокруг точки вставки. i чтобы получить первый k ближайшие элементы. Временная сложность этого решения O(n), куда n это размер ввода.

Мы также можем найти точку вставки i с использованием алгоритм бинарного поиска, который работает в O(log(n)) время. С момента обнаружения k ближайший элемент занимает O(k) время, общая временная сложность этого решения равна O(log(n) + k). Ниже приведена реализация на C, C++, Java и Python, основанная на этой идее:

C

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

#include <stdio.h>

#include <stdlib.h>

// Функция для поиска в указанном массиве `nums` ключа `target`

// используя алгоритм бинарного поиска

int binarySearch(int nums[], int n, int target)

{

    int low = 0;

    int high = n — 1;

    while (low <= high)

    {

        int mid = low + (high — low) / 2;

        if (nums[mid] < target) {

            low = mid + 1;

        }

        else if (nums[mid] > target) {

            high = mid — 1;

        }

        else {

            return mid;     // ключ найден

        }

    }

    return low;             // ключ не найден

}

// Функция для поиска `k` элементов, ближайших к `target`, в отсортированном целочисленном массиве `nums`

void findKClosestElements(int nums[], int target, int k, int n)

{

    // найти точку вставки с помощью алгоритма бинарного поиска

    int i = binarySearch(nums, n, target);

    int left = i — 1;

    int right = i;

    // запустить `k` раз

    while (k— > 0)

    {

        // сравниваем элементы по обе стороны от точки вставки `i`

        // чтобы получить первые `k` ближайших элементов

        if (left < 0 || (right < n &&

                abs(nums[left] — target) > abs(nums[right] — target))) {

            right++;

        }

        else {

            left—;

        }

    }

    // вывести `k` ближайших элементов

    left++;

    while (left < right)

    {

        printf(«%d «, nums[left]);

        left++;

    }

}

int main(void)

{

    int nums[] = { 10, 12, 15, 17, 18, 20, 25 };

    int n = sizeof(nums) / sizeof(nums[0]);

    int target = 16, k = 4;

    findKClosestElements(nums, target, k, n);

    return 0;

}

Скачать  Выполнить код

результат:

12 15 17 18

C++

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Функция для поиска `k` ближайших элементов к `target` в отсортированном целочисленном векторе `input`

vector<int> findKClosestElements(vector<int> const &input, int target, int k)

{

    // найти точку вставки с помощью алгоритма бинарного поиска

    int i = lower_bound(input.begin(), input.end(), target) — input.begin();

    int left = i — 1;

    int right = i;

    // запустить `k` раз

    while (k— > 0)

    {

        // сравниваем элементы по обе стороны от точки вставки `i`

        // чтобы получить первые `k` ближайших элементов

        if (left < 0 || (right < input.size() &&

                abs(input[left] — target) > abs(input[right] — target))) {

            right++;

        }

        else {

            left—;

        }

    }

    // вернуть `k` ближайших элементов

    return vector<int>(input.begin() + left + 1, input.begin() + right);

}

int main()

{

    vector<int> input = { 10, 12, 15, 17, 18, 20, 25 };

    int target = 16, k = 4;

    vector<int> result = findKClosestElements(input, target, k);

    for (int i: result) {

        cout << i << » «;

    }

    return 0;

}

Скачать  Выполнить код

результат:

12 15 17 18

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

import java.util.Arrays;

import java.util.Collections;

import java.util.List;

class Main

{

    // Функция для поиска `k` элементов, ближайших к `target`, в отсортированном списке `input`

    public static List<Integer> findKClosestElements(List<Integer> input, int k, int target)

    {

        // найти точку вставки с помощью алгоритма бинарного поиска

        int i = Collections.binarySearch(input, target);

        // Collections.binarySearch() возвращает `-(точка вставки) — 1`

        // если ключ не содержится в списке

        if (i < 0) {

            i = —(i + 1);

        }

        int left = i — 1;

        int right = i;

        // запустить `k` раз

        while (k— > 0)

        {

            // сравниваем элементы по обе стороны от точки вставки `i`

            // чтобы получить первые `k` ближайших элементов

            if (left < 0 || (right < input.size() &&

                    Math.abs(input.get(left) — target) > Math.abs(input.get(right) — target))) {

                right++;

            }

            else {

                left—;

            }

        }

        // вернуть `k` ближайших элементов

        return input.subList(left + 1, right);

    }

    public static void main(String[] args)

    {

        List<Integer> input = Arrays.asList(10, 12, 15, 17, 18, 20, 25);

        int target = 16, k = 4;

        System.out.println(findKClosestElements(input, k, target));

    }

}

Скачать  Выполнить код

результат:

[12, 15, 17, 18]

Python

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

# Функция для поиска в указанном массиве `nums` ключа `target`

# с использованием алгоритма бинарного поиска

def binarySearch(nums, target):

    low = 0

    high = len(nums) — 1

    while low <= high:

        mid = low + (high — low) // 2

        if nums[mid] < target:

            low = mid + 1

        elif nums[mid] > target:

            high = mid — 1

        else:

            return mid      # Ключ # найден

    return low              # Ключ # не найден

# Функция для поиска `k` элементов, ближайших к `target`, в отсортированном массиве целых чисел `nums`

def findKClosestElements(nums, target, k):

    # найти точку вставки с помощью алгоритма бинарного поиска

    i = binarySearch(nums, target)

    left = i — 1

    right = i

    # запускается `k` раз

    while k > 0:

        # сравнить элементы по обе стороны от точки вставки `i`

        #, чтобы получить первые `k` ближайших элементов

        if left < 0 or (right < len(nums) and abs(nums[left] — target) > abs(nums[right] — target)):

            right = right + 1

        else:

            left = left — 1

        k = k — 1

    # возвращает `k` ближайших элементов

    return nums[left+1: right]

if __name__ == ‘__main__’:

    nums = [10, 12, 15, 17, 18, 20, 25]

    target = 16

    k = 4

    print(findKClosestElements(nums, target, k))

Скачать  Выполнить код

результат:

[12, 15, 17, 18]

Приведенное выше решение для выполнения двоичного поиска, чтобы найти точку вставки, а затем пытается найти k ближайшие элементы. Однако мы можем объединить всю логику в одну процедуру бинарного поиска. Вот как алгоритм будет выглядеть в C, Java и Python:

C

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

#include <stdio.h>

#include <stdlib.h>

// Функция для поиска `k` элементов, ближайших к `target`, в отсортированном целочисленном массиве `nums`

void findKClosestElements(int nums[], int target, int k, int n)

{

    int left = 0;

    int right = n;

    while (right — left >= k)

    {

        if (abs(nums[left] — target) > abs(nums[right] — target)) {

            left++;

        }

        else {

            right—;

        }

    }

    // вывести `k` ближайших элементов

    while (left <= right)

    {

        printf(«%d «, nums[left]);

        left++;

    }

}

int main(void)

{

    int nums[] = { 10, 12, 15, 17, 18, 20, 25 };

    int n = sizeof(nums) / sizeof(nums[0]);

    int target = 16, k = 4;

    findKClosestElements(nums, target, k, n);

    return 0;

}

Скачать  Выполнить код

результат:

12 15 17 18

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

import java.util.Arrays;

import java.util.List;

import java.util.stream.Collectors;

class Main

{

    // Функция для поиска `k` элементов, ближайших к `target`, в отсортированном целочисленном массиве `nums`

    public static List<Integer> findKClosestElements(int[] nums, int k, int target)

    {

        int left = 0;

        int right = nums.length — 1;

        while (right — left >= k)

        {

            if (Math.abs(nums[left] — target) > Math.abs(nums[right] — target)) {

                left++;

            }

            else {

                right—;

            }

        }

        return Arrays.stream(nums, left, right + 1).boxed()

                .collect(Collectors.toList());

    }

    public static void main(String[] args)

    {

        int[] nums = {10, 12, 15, 17, 18, 20, 25 };

        int target = 16, k = 4;

        System.out.println(findKClosestElements(nums, k, target));

    }

}

Скачать  Выполнить код

результат:

[12, 15, 17, 18]

Python

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# Функция для поиска `k` элементов, ближайших к `target`, в отсортированном массиве целых чисел `nums`

def findKClosestElements(nums, k, target):

    left = 0

    right = len(nums) — 1

    while right — left >= k:

        if abs(nums[left] — target) > abs(nums[right] — target):

            left = left + 1

        else:

            right = right — 1

    return nums[left:left + k]

if __name__ == ‘__main__’:

    nums = [10, 12, 15, 17, 18, 20, 25]

    target = 16

    k = 4

    print(findKClosestElements(nums, k, target))

Скачать  Выполнить код

результат:

[12, 15, 17, 18]

Временная сложность приведенного выше решения равна O(n) и не требует дополнительного места.

Источник

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
5 is closest to 4 in given array

Input :arr[] = {2, 5, 6, 7, 8, 8, 9, 15, 19, 22, 32}; 
       Target number = 34
Output : 32
32 is closest to 34 in given array

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 absolute difference.

An efficient solution is to use Binary Search.  

C++

#include <bits/stdc++.h>

using namespace std;

int getClosest(int, int, int);

int findClosest(int arr[], int n, int target)

{

    if (target <= arr[0])

        return arr[0];

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

        return arr[n - 1];

    int 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 && target > arr[mid - 1])

                return getClosest(arr[mid - 1],

                                  arr[mid], target);  

            j = mid;

        }

        else {

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

                return getClosest(arr[mid],

                                  arr[mid + 1], target);

            i = mid + 1;

        }

    }

    return arr[mid];

}

int getClosest(int val1, int val2,

               int target)

{

    if (target - val1 >= val2 - target)

        return val2;

    else

        return val1;

}

int main()

{

    int arr[] = { 1, 2, 4, 5, 6, 6, 8, 8, 9 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int target = 11;

    cout << (findClosest(arr, n, target));

}

Java

import java.util.*;

import java.lang.*;

import java.io.*;

class FindClosestNumber {

    public static int findClosest(int arr[], int target)

    {

        int n = arr.length;

        if (target <= arr[0])

            return arr[0];

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

            return arr[n - 1];

        int 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 && target > arr[mid - 1])

                    return getClosest(arr[mid - 1],

                                  arr[mid], target);

                j = mid;             

            }

            else {

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

                    return getClosest(arr[mid],

                          arr[mid + 1], target);               

                i = mid + 1;

            }

        }

        return arr[mid];

    }

    public static int getClosest(int val1, int val2,

                                         int target)

    {

        if (target - val1 >= val2 - target)

            return val2;       

        else

            return val1;       

    }

    public static void main(String[] args)

    {

        int arr[] = { 1, 2, 4, 5, 6, 6, 8, 9 };

        int target = 11;

        System.out.println(findClosest(arr, target));

    }

}

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))

C#

using System;

class GFG

{

    public static int findClosest(int []arr,

                                  int target)

    {

        int n = arr.Length;

        if (target <= arr[0])

            return arr[0];

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

            return arr[n - 1];

        int 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 && target > arr[mid - 1])

                    return getClosest(arr[mid - 1],

                                 arr[mid], target);

                j = mid;            

            }

            else

            {

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

                    return getClosest(arr[mid],

                         arr[mid + 1], target);        

                i = mid + 1;

            }

        }

        return arr[mid];

    }

    public static int getClosest(int val1, int val2,

                                 int target)

    {

        if (target - val1 >= val2 - target)

            return val2;    

        else

            return val1;    

    }

    public static void Main()

    {

        int []arr = {1, 2, 4, 5,

                     6, 6, 8, 9};

        int target = 11;

        Console.WriteLine(findClosest(arr, target));

    }

}

PHP

<?php

function 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 && $target > $arr[$mid - 1])

                return getClosest($arr[$mid - 1],

                                  $arr[$mid], $target);

            $j = $mid;

        }

        else

        {

            if ($mid < $n - 1 &&

                $target < $arr[$mid + 1])

                return getClosest($arr[$mid],

                                  $arr[$mid + 1], $target);

            $i = $mid + 1;

        }

    }

    return $arr[$mid];

}

function getClosest($val1, $val2, $target)

{

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

        return $val2;

    else

        return $val1;

}

$arr = array( 1, 2, 4, 5, 6, 6, 8, 9 );

$n = sizeof($arr);

$target = 11;

echo (findClosest($arr, $n, $target));

?>

Javascript

<script>

function findClosest(arr, target)

{

    let n = arr.length;

    if (target <= arr[0])

        return arr[0];

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

        return arr[n - 1];

    let 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 && target > arr[mid - 1])

                return getClosest(arr[mid - 1],

                                  arr[mid], target);

            j = mid;             

        }

        else

        {

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

                return getClosest(arr[mid],

                                  arr[mid + 1],

                                  target);               

            i = mid + 1;

        }

    }

    return arr[mid];

}

function getClosest(val1, val2, target)

{

    if (target - val1 >= val2 - target)

        return val2;       

    else

        return val1;       

}

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

let target = 11;

document.write(findClosest(arr, target));

</script>

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

Approach 2: 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.

Initialize left = 0 and right = n-1, where n is the size of the array.
Loop while left < right
a. 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++
b. Else, move right pointer one step to the left, i.e. right–
Return arr[left], which will be the element closest to the target.

C++

#include <bits/stdc++.h>

using namespace std;

int findClosest(int arr[], int n, int target)

{

    int left = 0, right = n - 1;

    while (left < right) {

        if (abs(arr[left] - target)

            <= abs(arr[right] - target)) {

            right--;

        }

        else {

            left++;

        }

    }

    return arr[left];

}

int main()

{

    int arr[] = { 1, 2, 4, 5, 6, 6, 8, 8, 9 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int target = 11;

    cout << findClosest(arr, n, target);

    return 0;

}

Java

import java.util.*;

public class Main {

    public static int findClosest(int[] arr, int n,

                                  int target)

    {

        int left = 0, right = n - 1;

        while (left < right) {

            if (Math.abs(arr[left] - target)

                <= Math.abs(arr[right] - target)) {

                right--;

            }

            else {

                left++;

            }

        }

        return arr[left];

    }

    public static void main(String[] args)

    {

        int[] arr = { 1, 2, 4, 5, 6, 6, 8, 8, 9 };

        int n = arr.length;

        int target = 11;

        System.out.println(findClosest(arr, n, target));

    }

}

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))

C#

using System;

public class Program {

    static int FindClosest(int[] arr, int n, int target)

    {

        int left = 0, right = n - 1;

        while (left < right) {

            if (Math.Abs(arr[left] - target)

                <= Math.Abs(arr[right] - target)) {

                right--;

            }

            else {

                left++;

            }

        }

        return arr[left];

    }

    static void Main(string[] args)

    {

        int[] arr = { 1, 2, 4, 5, 6, 6, 8, 8, 9 };

        int n = arr.Length;

        int target = 11;

        Console.WriteLine(FindClosest(arr, n, target));

    }

}

Javascript

function findClosest(arr, n, target) {

  let left = 0, right = n-1;

  while (left < right) {

    if (Math.abs(arr[left] - target) <= Math.abs(arr[right] - target)) {

      right--;

    } else {

      left++;

    }

  }

  return arr[left];

}

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

const n = arr.length;

const target = 11;

console.log(findClosest(arr, n, target));

Time Complexity: O(N)
Auxiliary Space: O(1)

Approach 3: Recursive Approach

  • “findClosestRecursive” function takes an array “arr” , right and left indices of the current search range and integer traget.
  • “findClosestRecursive” function usese binary search approach to recursively search  array.
  • “findClosestRecursive” function also calculates the middle index of the current search range and recursively searches the left and right halves of the array.
  • Base case – It occurs when there is only one element in an array. In that case,  function will simply returns that element.

C++

#include <bits/stdc++.h>

using namespace std;

int findClosestRecursive(int arr[], int left, int right, int target) {

    if (left == right) {

        return arr[left];

    }

    int mid = (left + right) / 2;

    int leftClosest = findClosestRecursive(arr, left, mid, target);

    int rightClosest = findClosestRecursive(arr, mid + 1, right, target);

    if (abs(leftClosest - target) <= abs(rightClosest - target)) {

        return leftClosest;

    }

    else {

        return rightClosest;

    }

}

int main() {

    int arr[] = {1, 2, 4, 5, 6, 6, 8, 8, 9};

    int n = sizeof(arr) / sizeof(arr[0]);

    int target = 11;

    cout << findClosestRecursive(arr, 0, n-1, target);

    return 0;

}

Java

import java.util.*;

public class Main {

  public static int findClosestRecursive(int[] arr,

                                         int left,

                                         int right,

                                         int target)

  {

    if (left == right) {

      return arr[left];

    }

    int mid = (left + right) / 2;

    int leftClosest

      = findClosestRecursive(arr, left, mid, target);

    int rightClosest = findClosestRecursive(

      arr, mid + 1, right, target);

    if (Math.abs(leftClosest - target)

        <= Math.abs(rightClosest - target)) {

      return leftClosest;

    }

    else {

      return rightClosest;

    }

  }

  public static void main(String[] args)

  {

    int[] arr = { 1, 2, 4, 5, 6, 6, 8, 8, 9 };

    int n = arr.length;

    int target = 11;

    System.out.println(

      findClosestRecursive(arr, 0, n - 1, target));

  }

}

Javascript

function findClosestRecursive(arr, left, right, target) {

    if (left == right) {

        return arr[left];

    }

    let mid = Math.floor((left + right) / 2);

    let leftClosest = findClosestRecursive(arr, left, mid, target);

    let rightClosest = findClosestRecursive(arr, mid + 1, right, target);

    if (Math.abs(leftClosest - target) <= Math.abs(rightClosest - target)) {

        return leftClosest;

    } else {

        return rightClosest;

    }

}

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

let n = arr.length;

let target = 11;

console.log(findClosestRecursive(arr, 0, n - 1, target));

Time Complexity: O(log n)
Auxiliary Space: O(log n)

Last Updated :
19 Apr, 2023

Like Article

Save Article

Источник

За последние 24 часа нас посетили 11915 программистов и 973 робота. Сейчас ищут 750 программистов …


  1. dsda

    dsda
    Активный пользователь

    С нами с:
    3 сен 2008
    Сообщения:
    34
    Симпатии:
    0

    Подскажите алгоритм поиска ближайших значений массива по отношению к заданному.

    Тоесть есть массив

    1. for ($x=0;$x<=99;$x++) { $arr[]=rand(1,100); }

    и значение допустим 50 и надо найти элемент массива к значению которого эта переменная максимально близка.


  2. sylex

    sylex
    Активный пользователь

    С нами с:
    9 ноя 2008
    Сообщения:
    625
    Симпатии:
    0
    Адрес:
    Омск

    dsda
    циклом перебор, простой алгоритм блин


  3. dsda

    dsda
    Активный пользователь

    С нами с:
    3 сен 2008
    Сообщения:
    34
    Симпатии:
    0

    это я понимаю. подскажите сам алгоритм. а то я что-то туплю =(


  4. TheShock

    TheShock
    Активный пользователь

    С нами с:
    30 май 2009
    Сообщения:
    1.255
    Симпатии:
    0
    Адрес:
    Київ

    Что тут тупить то?

    8. function searchNearest ($value, $inArray) {
    11.     foreach ($inArray as $k => $v) {
    15.         $dif = abs ($value — $v);
    16.         if (is_null($lastKey) || $dif < $lastDif) {
    23. echo searchNearest(40, $arr), «n«;

    возвращает ключ массива, по которому ближайшее значение


  5. sylex

    sylex
    Активный пользователь

    С нами с:
    9 ноя 2008
    Сообщения:
    625
    Симпатии:
    0
    Адрес:
    Омск

    5. for ($x=0;$x<=29;$x++) { $arr[]=rand(1,100); }
    13. foreach ($arr as $k => $v) {
    22. echo «<br><br>poisk {$e} = index element {$i}, value {$val}«;


  7. kostyl

    другое дело если массив отсортирован уже…


  8. dsda

    dsda
    Активный пользователь

    С нами с:
    3 сен 2008
    Сообщения:
    34
    Симпатии:
    0

    Спасибо большущее, буду разбираться что я неправильно делал.


  9. TheShock

    TheShock
    Активный пользователь

    С нами с:
    30 май 2009
    Сообщения:
    1.255
    Симпатии:
    0
    Адрес:
    Київ

    если массив отсортирован, то из массива длиной в 1’000’000 элементов достаточно получить 20 значений — это естественно. Но мы берем совершенно случайный массив ведь.

    sylex, спс :)


  10. kostyl

    TheShock
    Дык я о чем и говорю может быстрей отсортировать и найти? Ну смотря какого размера массив и какие там данные…


  11. TheShock

    TheShock
    Активный пользователь

    С нами с:
    30 май 2009
    Сообщения:
    1.255
    Симпатии:
    0
    Адрес:
    Київ

    kostyl, сомневаюсь, что есть смысл, если честно.


  12. TheShock

    TheShock
    Активный пользователь

    С нами с:
    30 май 2009
    Сообщения:
    1.255
    Симпатии:
    0
    Адрес:
    Київ

    Нету смысла. Мой алгоритм быстрее сортировки:

    4. for ($x = 150000; $x—;) {
    8. function searchNearest ($value, $inArray) {
    11.     foreach ($inArray as $k => $v) {
    15.         $dif = abs ($value — $v);
    16.         if (is_null($lastKey) || $dif < $lastDif) {
    23. echo ‘length     : ‘ , count($arr) , «n«;
    27. echo ‘key        : ‘, searchNearest(40, $arr), «n«;
    28. echo ‘key search : ‘, (microtime(1) — $s), «n«;
    33. echo ‘array sort : ‘, (microtime(1) — $s), «n«;
    1. $ php -f searchNearest.php
    4.  key search : 0.189264059067
    5.  array sort : 0.320148944855
    7. $ php -f searchNearest.php
    10.  key search : 0.189424991608
    11.  array sort : 0.31040596962
    13. $ php -f searchNearest.php
    16.  key search : 0.233227014542
    17.  array sort : 0.339351892471
    19. $ php -f searchNearest.php
    22.  key search : 0.215394973755
    23.  array sort : 0.318609952927
    25. $ php -f searchNearest.php
    28.  key search : 0.19428396225
    29.  array sort : 0.314887046814


  15. kostyl

    TheShock
    относительно меня ты становишься менее линивым. Я тоже раньше не мог удержаться, а сейчас лень.

Источник

Требуется реализовать поиск в отсортированном массиве элемента, ближайшего к заданному значению.
В первой строке записано одно целое число N — размер отсортированного массива
(1 <= N <= 10^5). Далее записаны элементы массива ( N целых чисел, |Ai| <= 10^9). Затем
записано целое число Q— количество запросов, которые нужно обработать (1 <= Q <= 10^5). В остальных Q строках записаны целые числа Yj, определяющие запросы на поиск.
Запросы нужно обрабатывать следующим образом. Для каждого числа Yj нужно найти
в массиве A такой элемент, чтобы разность между ним и Yj была минимальной. В выходной
файл нужно вывести два целых числа через пробел: индекс найденного элемента и полученное минимальное расстояние.
Элементы массива нумеруются индексами от 0 до N − 1. Если ближайших элементов
несколько, разрешается выводить индекс любого из них. В данной задаче ответ для каждого запроса нужно находить независимо от всех
остальных запросов за время O(log N) в худшем случае.
Существует ли какое-то красивое решение?


  • Вопрос задан

    более двух лет назад

  • 779 просмотров

Источник

Понравилась статья? Поделить с друзьями:

Не пропустите также:

  • Как составить поликарбонат
  • Как найти всех культистов боги эгейского моря
  • Как найти жену если тебе за 60
  • Как найти многоквартирный дом на кадастровой карте
  • Как найти загруженные фото в интернете

    • 0 0 голоса
    Рейтинг статьи
    Подписаться
    Уведомить о
    guest

    0 комментариев
    Старые
    Новые Популярные
    Межтекстовые Отзывы
    Посмотреть все комментарии