Ternary search


Download 82.87 Kb.
bet1/2
Sana14.12.2022
Hajmi82.87 Kb.
#1007107
  1   2
Bog'liq
Ahmadjonova Zarnigora


Ternary search
Ternary search - bu massivdagi elementni topish uchun ishlatilishi mumkin bo'lgan kamaytirish (doimiy) va zabt etish algoritmi. Bu Binary searchga o'xshaydi, bu erda biz massivni ikki qismga ajratamiz, lekin bu algoritmda biz berilgan massivni uch qismga ajratamiz va qaysi birida kalit (biz izlayotgan element) borligini aniqlaymiz. Quyida ko'rsatilgandek hisoblanishi mumkin bo'lgan mid1 va mid2 ni olib, massivni uch qismga bo'lishimiz mumkin. Dastlab, l va r mos ravishda 0 va n-1 bo'ladi, bu erda n - massivning uzunligi.
mid1 = l + (r-l)/3 
mid2 = r – (r-l)/3 
Eslatma: Massivda Ternary Searchni amalga oshirish uchun uni tartiblash kerak.

Ternary Searchni amalga oshirish uchun qadamlar:

  • Birinchidan, kalitni o'rtadagi element bilan solishtiring1. Agar biz tenglikni topsak, 1 ning o'rta nuqtasini qaytaramiz.

  • Agar yo'q bo'lsa, kalitni o'rtadagi element bilan solishtiring2. Agar biz tenglikni topsak, 2 ning o'rta nuqtasini qaytaramiz.

  • Agar yo'q bo'lsa, kalit o'rtadagi elementdan kichik yoki yo'qligini tekshiring1. Ha bo'lsa, birinchi qismga takrorlang.

  • Agar yo'q bo'lsa, kalit o'rtadagi elementdan kattaroq yoki yo'qligini tekshiring2. Ha bo'lsa, uchinchi qismga qayting.

  • Agar yo'q bo'lsa, biz ikkinchi (o'rta) qismga qaytamiz.

Misol:

Ternary search ning rekursiv amalga oshirilishi:
/*
 * Created by SharpDevelo .
 * User: User
 * Date: Сб 04.06.22
 * Time: 12:22
 * 
 * To change this template use Tools | Options | Coding | Edit Standard Headers.
 */
using System;

class GFG {

// Function to perform Ternary Search
static int ternarySearch(int l, int r, int key, int[] ar)
{
if (r >= l) {

// Find the mid1 and mid2



Download 82.87 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling