Número de ocorrencias por busca binária

8 de novembro de 2011 8 respostas

LucasAdri07 8 de novembro de 2011

Boa tarde pessoal, estou com um problema ao realizar uma busca no número de ocorrencias por busca binária.

A classe está em VB, mas acho que vocês podem dar uam força.

Public Function getOcorrencia(ByVal numero As Integer) As Integer
        Dim meio As Integer
        Dim min As Integer
        Dim max As Integer

        min = 0
        max = nome.GetUpperBound(0)


        While min <= max
            meio = (min + max) \ 2

            If numero = nome(meio) Then
                Return meio
            ElseIf numero < nome(meio) Then
                max = meio - 1
            Else
                min = meio + 1
            End If

        End While

        Return -1

    End Function

Gostaria de saber o que preciso implementar nessa classe pra ela achar o número de ocorrencias na busca.

Por exemplo, se eu digitar e mandar gravar no meu ListBox essa sequencia.

1
7
8
1
2
3
4
8

E depois de ordenada eu quiser saber o número de ocorrencias do número 1 dentro do ListBox, o que é preciso eu fazer.

Grato, Lucas

8 Respostas

LucasAdri07 9 de nov. de 2011

Ninguém?

ruivo 9 de nov. de 2011

Cara, a busca binária não é o melhor caso para essa sua situação. O algoritmo da busca binária, ao encontrar o elemento procurado, pára.
Se assim não o fizesse, o algoritmo nunca saberia quando parar.

LucasAdri07 9 de nov. de 2011

ruivo:
Cara, a busca binária não é o melhor caso para essa sua situação. O algoritmo da busca binária, ao encontrar o elemento procurado, pára.
Se assim não o fizesse, o algoritmo nunca saberia quando parar.

Certeza que não tem como buscar o número de ocorrencias?

O exercicio que o professor passou ele pediu para buscarmos o número de ocorrencias do valor procurado…

pmlm 9 de nov. de 2011

Depois de encontrares o número, com a tua busca binária, só tens de contar quantos iguais tens antes e quantos tens depois…

LucasAdri07 9 de nov. de 2011

O problema é que realmente não consegui achar um jeito de comparar o número com algo para poder achar as ocorrencias…

Tem como dar uma luz?

LucasAdri07 9 de nov. de 2011

Consegui obter o número de ocorrências através disso.

Public Function getOcorrencia(ByVal numero As Integer) As Integer
        Dim ocorrencias As Integer = 0
        For i = 0 To numero
            If (Me.nome(i) = numero) Then ocorrencias = ocorrencias + 1
        Next

        Return ocorrencias

    End Function

O único problema é que não consigo trabalhar com números com mais de 1 algarismo, teria um modo de tratá-lo?

LucasAdri07 9 de nov. de 2011

E também não consigo fazer essa busca binária por String, exemplo:

Lucas
Robson
Robson
Carlos
Lucas

Eu consigo ordenalo, mas não consigo dar o número de ocorrencias…

LucasAdri07 9 de nov. de 2011

Para melhor analise segue minha classe:

Public Class Classifica
    Private nome(10) As String
    Private indice As Integer = -1

    Public Function setNome(ByVal nome As String) As Boolean
        Dim cheio As Boolean = False
        indice = indice + 1
        Me.nome(indice) = nome
        If indice = 9 Then cheio = True
        Return cheio
    End Function

    Public Sub zeraArray()
        For i = 0 To indice
            nome(i) = ""
        Next
        indice = -1
    End Sub

    Public Function getNome() As String()
        Return Me.nome
    End Function

    Public Function getIndice() As Integer
        Return Me.indice
    End Function

    Public Sub ordenaArray()
        Dim nome As String
        If (Me.indice < 0) Then Exit Sub
        For j = 0 To Me.indice
            nome = Me.nome(j)
            For i = j To Me.indice
                If (Me.nome(i) < nome) Then
                    nome = Me.nome(j)
                    Me.nome(j) = Me.nome(i)
                    Me.nome(i) = nome
                End If
            Next
        Next

    End Sub
    Public Function getPesquisa(ByVal numero As Integer) As Integer
        Dim meio As Integer
        Dim min As Integer
        Dim max As Integer

        min = 0
        max = nome.GetUpperBound(0)


        While min <= max
            meio = (min + max) \ 2

            If numero = nome(meio) Then
                Return meio
            ElseIf numero < nome(meio) Then
                max = meio - 1
            Else
                min = meio + 1
            End If

        End While

        Return -1
        
    End Function

    Public Function getOcorrencia(ByVal numero As Integer) As Integer
        Dim ocorrencias As Integer = 0
        For i = 0 To numero
            If (Me.nome(i) = numero) Then ocorrencias = ocorrencias + 1
        Next

        Return ocorrencias

    End Function

End Class

Criado 8 de novembro de 2011

Ultima resposta 9 de nov. de 2011

Respostas 8

Participantes 3

8 Respostas

Topicos relacionados