powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Поиск в массиве
11 сообщений из 11, страница 1 из 1
Поиск в массиве
    #32641065
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пожалуйста, помогите, кто сколько сможет :-).

Срочно нужен алгоритм поиска делением пополам в упорядоченном массиве...

В институте учил давно, забыл :-), а в работе не попадался...

Спасибо.
...
Рейтинг: 0 / 0
Поиск в массиве
    #32641107
marvan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: plaintext
1.
Option ExplicitDim words(0 To 100) As StringDim upbound As IntegerDim lobound As IntegerDim numrec As IntegerDim curmid As IntegerDim currec As IntegerDim counta As IntegerDim filenum As IntegerPrivate Sub cmdSearch_Click()currec = 0txtSearch.Text = UCase(txtSearch.Text)    Do While upbound <> lobound \'Make sure the loop will end if no result is found    \'Check to see it the word is at the middle position    If words(curmid) = txtSearch.Text Then currec = curmid: Exit Do    \'Check to see if the word falls before or after the middle of the list    If words(curmid) > txtSearch.Text Then      upbound = curmid    ElseIf words(curmid) < txtSearch Then      lobound = curmid    End If    \'set where the new middle is    curmid = (upbound - (lobound - 1)) \\ 2 + lobound    If lobound = curmid Or upbound = 1 Then Exit Do  Loop    If currec = 0 Then    MsgBox "Record Not Found"  Else    MsgBox txtSearch.Text & " found in" & vbCrLf & "Position: " & currec  End If  numrec = 100  lobound = 1  upbound = 100  curmid = (upbound - (lobound - 1)) \\ 2End SubPrivate Sub Form_Load()  filenum = FreeFile  Open App.Path & "\\sorted.txt" For Input As filenum  For counta = 1 To 100    Input #filenum, words(counta)    List1.AddItem words(counta)  Next counta  MsgBox "Words Loaded"  numrec = 100  lobound = 0  upbound = 100  curmid = (upbound - (lobound - 1)) \\ 2End Sub
Как отформатирован этот код?
...
Рейтинг: 0 / 0
Поиск в массиве
    #32641119
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Благодарю!

Я спасен.
...
Рейтинг: 0 / 0
Поиск в массиве
    #32641359
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пардон, marvan один вопрос


Первый раз Вы инициализуете переменные как:

Код: plaintext
1.
2.
3.
  numrec =  100 
 lobound =  0 
upbound =  100 
curmid = (upbound - (lobound -  1 )) \  2 

А второй раз как:
Код: plaintext
1.
2.
3.
4.
 numrec =  100 
 lobound =  1 
 upbound =  100 
 curmid = (upbound - (lobound -  1 )) \  2 

Почему не одно и то же?
Сначала 0, а потом 1?
В чем смысл разделения, поясните пожалуйста.
...
Рейтинг: 0 / 0
Поиск в массиве
    #32641382
marvan
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
это не мой код. головой думать лень
предпологаю, что это позволит вести поиск в массиве из одного элемента
вот ещё пример (тоже не мой) - может поможет
Код: plaintext
1.
\' Returns the position that the item was found at or -1 if not found.Function binarySearch(Table, Target, First As Integer, Last As Integer) As Integer  Dim Middle As Integer  While (First <= Last)    Middle = (First + Last) / 2    If Table(Middle) = Target Then      binarySearch = Middle      Exit Function    Else        If Table(Middle) < Target Then            First = Middle + 1        Else            Last = Middle - 1        End If    End If  Wend  binarySearch = -1End Function
Как отформатирован этот код?
...
Рейтинг: 0 / 0
Поиск в массиве
    #32641440
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
автор
предпологаю, что это позволит вести поиск в массиве из одного элемента


Да по-моему один фиг, только граница начала поиска на единицу смещается...

А судя по тому, что нумерация у автора начинается с 1, то оставлю-ка я единицу в обоих случаях, т.к. одного элемента в массиве, у меня, к сожалению, не будет :-). Дело к 100 000 подходит...

Спасибо и за второй вариант, но пока вроде и первый работает, как надо.
...
Рейтинг: 0 / 0
Поиск в массиве
    #32641471
Hibernate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
если делить не попалам, а на (1+5^0.5)/2 что примерно равно 0.618, то должно сходиться быстрее - к сож, не помню точно обоснования, но у Кнута такой вариант есть.
...
Рейтинг: 0 / 0
Поиск в массиве
    #32642280
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2Hibernate
Благодарю!
...
Рейтинг: 0 / 0
Поиск в массиве
    #32642466
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2All в первом варианте обнаружен глюк!!!
Почему-то на некоторых позициях обнаруживается полное зависание...

Вот так работает:

Код: plaintext
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.
  lobound =  1 
  upbound = mDimension
  curmid = (upbound + lobound) /  2 

  Item = - 1 
  currec =  0 
  
  Do While True
        If vntIndexKey = mWareNames(curmid) Then
             ' Найдено! Выходим... 
            currec = curmid
            Exit Do
        ElseIf vntIndexKey >= mWareNames(curmid) Then
            If lobound = curmid Then
               lobound = upbound
            Else
                lobound = curmid
            End If
        Else
            If upbound = curmid Then Exit Do
            upbound = curmid
        End If
      ' делим пополам, или кому как нравиться :-) 
        curmid = (upbound + lobound) /  2 
  Loop
  
  If currec =  0  Then
    Item = - 1 
  Else
    Item = mWareCodes(currec)
  End If



В принципе, это и есть второй вариант :-).

Всем спасибо.
...
Рейтинг: 0 / 0
Поиск в массиве
    #32642528
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Опечатка...

Вместо

Код: plaintext
1.
curmid = (upbound + lobound) \  2 

Следует читать


Код: plaintext
1.
curmid = (upbound + lobound) /  2 
...
Рейтинг: 0 / 0
Поиск в массиве
    #32642533
Дурак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
:-)

Все, блин, пора обедать... НАОБОРОТ!!!
...
Рейтинг: 0 / 0
11 сообщений из 11, страница 1 из 1
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Поиск в массиве
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]