Qidiruv algoritmlari chiziqli qidiruv va ikkilik qidiruv kodini amalga oshirish va murakkablik tahlili

O'rtacha holat: O'rtacha, maqsad element massivning biror joyida bo'ladi. Shunday qilib, vaqt murakkabligi bo'ladi O(logN).
Eng yomon holat maqsad element ro'yxatda bo'lmaganda yoki u o'rta elementdan uzoqda bo'lganda yuzaga keladi. Shunday qilib, vaqt murakkabligi bo'ladi O(logN).
Vaqtning murakkabligini qanday hisoblash mumkin:
Aytaylik, Ikkilik qidiruvdagi iteratsiya k marta takrorlangandan keyin tugaydi .
Har bir iteratsiyada massiv yarmiga bo'linadi. Deylik, har qanday iteratsiyada massiv uzunligi N ga teng .
1 -iteratsiyada ,
Length of array = N
2- iteratsiyada ,
Length of array = N/2
3- iteratsiyada ,
Length of array = (N/2)/2 = N/2^2
k takrorlashda ,
Length of array = N/2^k
Bundan tashqari, biz bilamizki, k bo'linishdan keyin massiv uzunligi 1 ga aylanadi : Massiv uzunligi = N⁄ ₂ ^k = 1 => N = 2 ^k
Agar log funktsiyasini ikkala tomondan qo'llasak: log ₂ (N) = log ₂ (2 ^k ) => log ₂ (N) = k log ₂ (2)
Sifatida (log _a (a) = 1)
Shuning uchun, => k = log ₂ (N)
Shunday qilib, endi biz Binary Searchning vaqt murakkabligi nima uchun log ₂ (N) ekanligini ko'rishimiz mumkin.
Bundan tashqari , Dipesh Patil - Algoritms Visualizer tomonidan qurilgan oddiy vosita yordamida yuqoridagi ikkita algoritmni tasavvur qilishingiz mumkin .
Buyurtma-agnostik ikkilik qidiruv
Aytaylik, tartiblangan massivda maqsadli elementni topishimiz kerak. Biz massivning tartiblanganligini bilamiz, lekin u o‘sish yoki kamayish tartibida tartiblanganligini bilmaymiz.
Buyurtma-agnostik Ikkilik qidiruvga yondashuv
Amalga oshirish ikkilik qidiruvga o'xshaydi, bundan tashqari biz massiv o'sish yoki kamayish tartibida tartiblanganligini aniqlashimiz kerak. Bu bizga massivning chap yarmida yoki massivning o'ng yarmida qidirishni davom ettirish haqida qaror qabul qilish imkonini beradi.

• 
  Biz birinchi navbatda maqsadni o'rta element bilan taqqoslaymiz
  
• 
  Agar massiv o'sish tartibida tartiblangan bo'lsa va maqsad o'rta elementdan kichik bo'lsa YOKI massiv kamayish tartibida tartiblangan va maqsad o'rta elementdan katta bo'lsa, u holda qidirishni massivning pastki yarmida sozlash orqali davom ettiramiz end=mid-1.
  
• 
  Aks holda, qidirishni massivning yuqori yarmida sozlash orqali amalga oshiramizstart=mid+1
  

Biz qilishimiz kerak bo'lgan yagona narsa, massiv o'sish yoki kamayish tartibida tartiblanganligini aniqlashdir. Buni massivning birinchi va oxirgi elementlarini solishtirish orqali osongina topishimiz mumkin.
if arr[0] < arr[arr.length-1]
array is sorted in ascending order
else
array is sorted in descending order