De halveren module in Python biedt eenvoudige en snelle (binaire zoekgebaseerde) functies om een ​​element in een gesorteerde lijst te doorzoeken, de juiste positie te vinden om nieuwe elementen in te voegen en nieuwe elementen in te voegen, zodat de lijst gesorteerd blijft.

Waarom hebben we de Bisect-module nodig?

1. Handig voor binaire zoekbewerkingen om in een gesorteerde lijst te zoeken en invoegpunten te lokaliseren.
2. Biedt efficiënte methoden om elementen in een gesorteerde lijst in te voegen, terwijl de volgorde behouden blijft.
3. Vermijdt de noodzaak van handmatig sorteren na elke invoeging, wat tijd en moeite bespaart.
4. Biedt functies zoals bisect() bisect_left() bisect_right() en insort() voor schone, geoptimaliseerde code.
5. Ideaal voor taken zoals het onderhouden van ranglijstgegevens of elk scenario waarbij gesorteerde gegevens worden ingevoegd/gezocht.

Kernfuncties van Bisect-module

De bisect-module biedt hoofdzakelijk twee soorten functionaliteiten:

• Het invoegpunt zoeken (zonder invoeging)
• Elementen op de juiste positie plaatsen

1. Invoegpunten zoeken

Deze functies retourneren de index waar het nieuwe element moet worden ingevoegd om de lijst gesorteerd te houden.

a) halveren.bisect(): Retourneert het meest rechtse invoegpunt voor het element. Als het element al bestaat, bevindt het invoegpunt zich na de bestaande vermeldingen.

bisect.bisect(lijst aantal beg=0 end=len(lijst))

Parameter:

• lijst: Gesorteerde lijst.
• nummer: Element om in te voegen.
• smeek: Startindex voor zoeken (optioneel).
• einde: Eindindex voor zoeken (optioneel).

b) halveren.bisect_left(): Retourneert het meest linkse invoegpunt voor het element. Als het element bestaat, bevindt het invoegpunt zich vóór de bestaande vermeldingen.

bisect.bisect_left(lijst aantal beg=0 end=len(lijst))

c) halveren.bisect_right(): Identiek aan bisect.bisect() retourneert het meest rechtse invoegpunt.

bisect.bisect_right(lijst aantal beg=0 end=len(lijst))

Voorbeeld: Zoek invoegindexen voor de waarde 4 in een gesorteerde lijst met behulp van verschillende deelfuncties.

   import   bisect   li   =   [  1     3     4     4     4     6     7  ]   print  (  bisect  .  bisect  (  li     4  ))   # right   print  (  bisect  .  bisect_left  (  li     4  ))   # left   print  (  bisect  .  bisect_right  (  li     4     0     4  ))   # subright   

5 2 4  

Uitleg:

• halveren (li 4): Retourneert 5 omdat het de meest rechtse positie vindt na de laatste 4 in de lijst (index 4), dus het invoegpunt is 5.
• halveren_links(li 4): Retourneert 2 omdat het de meest linkse positie vóór de eerste 4 in de lijst vindt (index 2).
• halveren_rechts(li 4 0 4): Werkt alleen op sublijst dat[0:4] en retourneert 4 omdat het 4 invoegt na de laatste 4 in de sublijst.

2. Elementen invoegen

Deze functies plaatsen het element op de juiste positie om het sorteren te behouden.

a) halveren.insort(): Voegt het element op de meest rechtse positie in. In tegenstelling tot bisect()-functies wijzigt dit feitelijk de lijst door het element in te voegen.

bisect.insort(lijst aantal beg=0 end=len(lijst))

Parameter:

• lijst: Gesorteerde lijst.
• nummer: Element om in te voegen.
• bedelen (optioneel): Startindex voor invoeging (standaard 0).
• einde (optioneel): Eindindex voor invoeging (standaard len(lijst)).

b) halveren.insort_left(): Voegt het element op de meest linkse positie in.

bisect.insort_left(lijst aantal beg=0 end=len(lijst))

c) halveren.insort_right(): Voegt het element op de meest rechtse positie in (vergelijkbaar met insort()).

bisect.insort_right(lijst aantal beg=0 end=len(lijst))

Voorbeeld: Voeg de waarde 5 in een gesorteerde lijst in en houd deze gesorteerd met behulp van verschillende invoegstrategieën.

   import   bisect   l1   =   [  1     3     4     4     4     6     7  ]   l2   =   [  1     3     4     4     4     6     7  ]   l3   =   [  1     3     4     4     4     6     7  ]   bisect  .  insort  (  l1     5  )   # right   print  (  l1  )   bisect  .  insort_left  (  l2     5  )   # left   print  (  l2  )   bisect  .  insort_right  (  l3     5     0     4  )   # subright   print  (  l3  )   

[1 3 4 4 4 5 6 7] [1 3 4 4 4 5 6 7] [1 3 4 4 5 4 6 7]  

Uitleg:

• ontstaan(l1 5) voegt 5 in op de meest rechtse geschikte positie – na alle 4s en vóór 6.
• insort_left(l2 ​​5) voegt 5 in op de meest linkse geschikte positie – hetzelfde als hier insorteren, aangezien 5 niet in de lijst staat.
• insort_right(l3 5 0 4) voegt 5 in bij index 4 en werkt alleen op sublijst l3[0:4] = [1 3 4 4] na de laatste ≤ 5 in dat bereik zonder de rest van de lijst te beïnvloeden.