Qidiruv va xeshlash algoritmlar. Qidiruv algoritmlar: chiziqli algoritm, binary qidiruv algoritmi

Masalan: chiziqli qidiruvga oid misol

2-misol: chiziqli qidiruv

Ikkilik qidiruv

• 
  left va right index lari markazidagi elementni topamiz (left + right) / 2
  
• 
  topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
  
• 
  agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
  
• 
  agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.
  

chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n)

Ikkilik (Binar) qidiruv

Jump (sakrab) qidirish algoritmi

• 
  Ikkilik qidiruv singari, Jump Search ham saralangan massivlarni qidirish algoritmidir.
  
• 
  Asosiy g'oya shundan iboratki, kamroq elementlarni tekshirish (chiziqli qidiruvdan ko'ra) sakrash qadamlar bilan tekshirish yoki barcha elementlarni qidirish o'rniga ba'zi elementlarni o'tkazib yuborish. Faqat tartiblangan massivlarda ishlaydi. Sakrab o'tiladigan blokning optimal hajmi (√ n).
  
• 
  Algorimning samaradorligi O (√ n)
  
• 
  Jump Search samaradorligi Liner Search
  

((O (n)) va Binary Search (O (Log n)) o'rtasida. https://www.geeksforgeeks.org/jump-search/

lys[0], lys[0+jump], lys[0+2jump], lys[0+3jump] va x.

Interpolation search

• 
  Линейный поиск находит элемент за O (n) раз, Jump Search занимает O (√ n) раз, а двоичный поиск занимает O (Log n) времени. Поиск с интерполяцией является усовершенствованием по сравнению с двоичным поиском для экземпляров, в которых значения в отсортированном массиве равномерно распределены. Двоичный поиск всегда переходит к среднему элементу для проверки. С другой стороны, поиск с интерполяцией может идти в разные места в соответствии со значением ключа, по которому выполняется поиск. Например, если значение ключа ближе к последнему элементу, поиск с интерполяцией, скорее всего, начнется с конца. Чтобы найти позицию для поиска, он использует следующую формулу.