Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Visual Basic [игнор отключен] [закрыт для гостей] / Поиск в массиве / 11 сообщений из 11, страница 1 из 1
09.08.2004, 14:45
    #32641065
Дурак
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск в массиве
Пожалуйста, помогите, кто сколько сможет :-).

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

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

Спасибо.
...
Рейтинг: 0 / 0
09.08.2004, 15:04
    #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
09.08.2004, 15:08
    #32641119
Дурак
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск в массиве
Благодарю!

Я спасен.
...
Рейтинг: 0 / 0
09.08.2004, 16:54
    #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
09.08.2004, 17:04
    #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
09.08.2004, 17:27
    #32641440
Дурак
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск в массиве
автор
предпологаю, что это позволит вести поиск в массиве из одного элемента


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

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

Спасибо и за второй вариант, но пока вроде и первый работает, как надо.
...
Рейтинг: 0 / 0
09.08.2004, 17:43
    #32641471
Hibernate
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск в массиве
если делить не попалам, а на (1+5^0.5)/2 что примерно равно 0.618, то должно сходиться быстрее - к сож, не помню точно обоснования, но у Кнута такой вариант есть.
...
Рейтинг: 0 / 0
10.08.2004, 11:28
    #32642280
Дурак
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск в массиве
2Hibernate
Благодарю!
...
Рейтинг: 0 / 0
10.08.2004, 12:40
    #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
10.08.2004, 13:07
    #32642528
Дурак
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Поиск в массиве
Опечатка...

Вместо

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

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


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

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


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