3 / 3 / 1
Регистрация: 04.04.2018
Сообщений: 351
1

Бинарный поиск числа в упорядоченном массиве

04.04.2018, 17:07. Показов 6184. Ответов 10
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Написать бинарный поиск искомого числа(введенного пользователем) в отсортированном массиве. Написать это всё в модуле.
Сам прекрасно понимаю на словах как работает бинарный поиск но написать на VBA не могу.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.04.2018, 17:07
Ответы с готовыми решениями:

Бинарный поиск числа в упорядоченном массиве
В упорядоченном массиве надо найти число. Программа должна выполняться с рекурсией

В одномерном массиве состоящем из n вещественных элементов сделать бинарный поиск числа А в упорядоченном массиве
Всем привет помогите решить задачи 1) В одномерном массиве состоящем из n вещественных элементов:...

Бинарный поиск в упорядоченном массиве
Задали реализовать бинарный поиск в упорядоченном массиве.Уже пол дня творю,3 листа исписал и...

Бинарный поиск в упорядоченном по возрастанию массиве
9 лаб.работа Бинарный поиск в упорядоченном по возрастанию массиве

10
Заблокирован
04.04.2018, 17:48 2
Ну напиши хотя-бы про сортированный массив да нам покажи - вдруг кто сподобится продолжить...
0
3 / 3 / 1
Регистрация: 04.04.2018
Сообщений: 351
04.04.2018, 18:44  [ТС] 3
Вот, прикрепил фото.
Не суть в массиве, любой массив.
Желательно чтобы ещё объяснения написали строчек кода если можно.
Миниатюры
Бинарный поиск числа в упорядоченном массиве  
0
oh my god
1454 / 793 / 161
Регистрация: 05.01.2016
Сообщений: 2,307
Записей в блоге: 8
04.04.2018, 20:47 4
Двоичный поиск VB6
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36587 / 20317 / 4218
Регистрация: 12.02.2012
Сообщений: 33,614
Записей в блоге: 13
04.04.2018, 21:55 5
Вот. Функция BinSearch возвращает индекс элемента (если он найден) или -1, если элемента нет:

Visual Basic
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
Function BinSearch(A() As Integer, v As Integer) As Integer
     b% = LBound(A)
     e% = UBound(A)
     Do
        c% = (e% + b%) / 2
        If A(c%) = v Then
           BinSearch = c%
           Exit Function
        End If
        If (e% - b%) <= 1 Then
           BinSearch = -1
           Exit Function
        End If
        If A(c%) > v Then
           e% = c%
        Else
           b% = c%
        End If
     Loop
End Function
 
Sub test()
Dim X(1 To 10) As Integer
    For i% = 0 To 9
        X(i% + 1) = Array(2, 3, 6, 8, 11, 33, 40, 42, 54, 87)(i%)
    Next i%
    Debug.Print BinSearch(X, 8)    ' вывод 4
    Debug.Print BinSearch(X, 88)  ' -1
    Debug.Print BinSearch(X, 12)  ' -1
    Debug.Print BinSearch(X, 54)  ' 9
    Debug.Print BinSearch(X, 87)  '10
End Sub
0
6171 / 936 / 310
Регистрация: 25.02.2011
Сообщений: 1,367
Записей в блоге: 1
05.04.2018, 08:50 6
Цитата Сообщение от Catstail Посмотреть сообщение
Функция BinSearch
число 2 не находит

Visual Basic
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
Function BinSearch(a() As Long, v As Long) As Long
    Dim b As Long, e As Long, c As Long
    b = LBound(a)
    e = UBound(a)
    While e >= b
        c = (e + b + 1) \ 2
        If a(c) = v Then
            BinSearch = c
            Exit Function
        ElseIf a(c) > v Then
            e = c - 1
        Else
            b = c + 1
        End If
    Wend
    BinSearch = -1
End Function
 
Sub test()
    Dim x(1 To 10) As Long, i As Long
    For i = 0 To 9
        x(i + 1) = Array(2, 3, 6, 8, 11, 33, 40, 42, 54, 87)(i)
    Next i
    Debug.Print BinSearch(x, 1)     ' вывод -1
    Debug.Print BinSearch(x, 2)     ' 1
    Debug.Print BinSearch(x, 8)     ' 4
    Debug.Print BinSearch(x, 88)    ' -1
    Debug.Print BinSearch(x, 12)    ' -1
    Debug.Print BinSearch(x, 54)    ' 9
    Debug.Print BinSearch(x, 87)    '10
End Sub
1
Модератор
Эксперт функциональных языков программированияЭксперт Python
36587 / 20317 / 4218
Регистрация: 12.02.2012
Сообщений: 33,614
Записей в блоге: 13
05.04.2018, 09:12 7
А я бы так поступил (две проверки в начале могут многое сэкономить):

Visual Basic
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
Function BinSearch(A() As Integer, v As Integer) As Integer
     b% = LBound(A)
     e% = UBound(A)
     If A(b%) = v Then
           BinSearch = b%
           Exit Function
     End If
     If A(e%) = v Then
           BinSearch = e%
           Exit Function
     End If
     Do
        c% = (e% + b%) \ 2
        If A(c%) = v Then
           BinSearch = c%
           Exit Function
        End If
        If (e% - b%) <= 1 Then
           BinSearch = -1
           Exit Function
        End If
        If A(c%) > v Then
           e% = c%
        Else
           b% = c%
        End If
     Loop
End Function
0
oh my god
1454 / 793 / 161
Регистрация: 05.01.2016
Сообщений: 2,307
Записей в блоге: 8
05.04.2018, 12:17 8
Лучший ответ Сообщение было отмечено dimmarvel как решение

Решение

Более универсальная функция для поиска в упорядоченном массиве чисел

Visual Basic
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Public Function BSearchDbl&(arr, ByVal elm As Double)
    'Бинарный поиск
    Dim max&, min&, tmp&
    min = LBound(arr)
    max = UBound(arr)
    While min <= max
        BSearchDbl = (min + max) \ 2
        If elm < arr(BSearchDbl) Then
            max = BSearchDbl - 1
        ElseIf elm = arr(BSearchDbl) Then
            Exit Function
        ElseIf elm > arr(BSearchDbl) Then
            min = BSearchDbl + 1
        End If
        tmp = tmp + 1
    Wend
    BSearchDbl = -1
End Function


Полностью весь модуль с макросом сортировки и примером использования

Кликните здесь для просмотра всего текста
Visual Basic
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
Option Explicit
 
Sub Пример_использования()
    Dim i&, SimpleArray, sIsk$, index&
    
    ReDim SimpleArray(500)
    
    'Создаем массив со случайным набором цифр
    For i = 0 To UBound(SimpleArray):     SimpleArray(i) = Fix(Rnd * 100):      Next
    
    
    qSortVar SimpleArray '---Сортируем массив SimpleArray
    
    
    sIsk = InputBox("Введите число от 0 до 100"): Do While sIsk = "": Exit Sub: Exit Do: Loop
    
    
    index = BSearchDbl(SimpleArray, sIsk)
    
    
    MsgBox "Значение " & IIf(index < 0, "не ", "") & "найденно" & vbLf & "Индекс: " & index & vbLf & "Искомое : " & sIsk
    
    
End Sub
 
 
Sub qSortVar(arr, Optional ByVal min& = -1, Optional ByVal max&)
    'Быстрая сортировка
    Dim i&, j&, v, w
    If min < 0 Then min = LBound(arr): max = UBound(arr):
    i = min: j = max: v = arr((i + j) \ 2)
    Do Until i > j: Do While arr(i) < v: i = i + 1: Loop: Do While arr(j) > v: j = j - 1: Loop
        If (i <= j) Then w = arr(i): arr(i) = arr(j): arr(j) = w: i = i + 1: j = j - 1
    Loop
    If min < j Then qSortVar arr, min, j
    If i < max Then qSortVar arr, i, max
End Sub
 
 
Public Function BSearchDbl&(arr, ByVal elm As Double)
    'Бинарный поиск
    Dim max&, min&, tmp&
    min = LBound(arr)
    max = UBound(arr)
    While min <= max
        BSearchDbl = (min + max) \ 2
        If elm < arr(BSearchDbl) Then
            max = BSearchDbl - 1
        ElseIf elm = arr(BSearchDbl) Then
            Exit Function
        ElseIf elm > arr(BSearchDbl) Then
            min = BSearchDbl + 1
        End If
        tmp = tmp + 1
    Wend
    BSearchDbl = -1
End Function
2
3 / 3 / 1
Регистрация: 04.04.2018
Сообщений: 351
07.04.2018, 10:36  [ТС] 9
такой вопрос, для чего нужна переменная tmp
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
36587 / 20317 / 4218
Регистрация: 12.02.2012
Сообщений: 33,614
Записей в блоге: 13
07.04.2018, 10:53 10
fever brain, строка 10 может сыграть злую шутку. Числа с плавающей точкой лучше не сравнивать на равенство.
0
oh my god
1454 / 793 / 161
Регистрация: 05.01.2016
Сообщений: 2,307
Записей в блоге: 8
08.04.2018, 05:11 11
Цитата Сообщение от dimmarvel Посмотреть сообщение
для чего нужна переменная tmp
Можешь ее удалить, мне она нужна была в ходе разработки чтоб посчитать число проходов
тоесть если массив = 256 элементов то должно быть 7-8 проходов поиска

Цитата Сообщение от Catstail Посмотреть сообщение
Числа с плавающей точкой лучше не сравнивать на равенство
ну значит для чисел с пл. точкой нужно делать приближения
0
08.04.2018, 05:11
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.04.2018, 05:11
Помогаю со студенческими работами здесь

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

Рекурсия: бинарный поиск в упорядоченном массиве
Найти в упорядоченном массиве заданный элемент методом деления массива пополам (бинарный поиск)....

Поиск заданного элемента в упорядоченном массиве (бинарный поиск)
Заполнить одномерный массив из n элементов согласно таблицы. Размерность массива задать в виде...

Поиск заданного элемента в упорядоченном массиве(бинарный поиск)
Заполнить одномерный массив из n элементов по формуле приведенной в картинке. Размерность массива...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru