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

Kodni amalga oshirish
Keling, ushbu turdagi qidiruv algoritmini turli xil dasturlash tillarida qanday amalga oshirishimizni ko'rib chiqaylik.
Java-da chiziqli yoki ketma-ket qidiruv
package algorithms.searching;


public class LinearSearch {
public static void main(String[] args) {
int[] nums = {2, 12, 15, 11, 7, 19, 45};
int target = 7;
System.out.println(search(nums, target));


}


static int search(int[] nums, int target) {
for (int index = 0; index < nums.length; index++) {
if (nums[index] == target) {
return index;
}
}
return -1;
}
}
Pythonda chiziqli yoki ketma-ket qidiruv
def search(nums, target):
for i in range(len(nums)):
if nums[i] == target:
return i
return -1


if __name__ == '__main__':
nums = [2, 12, 15, 11, 7, 19, 45]
target = 7
print(search(nums, target))
Vaqt murakkabligi tahlili
Eng yaxshi holat maqsad element massivning birinchi elementi bo'lganda yuzaga keladi. Taqqoslashlar soni, bu holda, 1. Demak, vaqt murakkabligi O(1).
O'rtacha holat: O'rtacha, maqsad element massivning o'rtasida joylashgan bo'ladi. Taqqoslashlar soni, bu holda, N/2 bo'ladi. Shunday qilib, vaqt murakkabligi bo'ladi O(N)(doimiy e'tiborga olinmaydi).
Eng yomon holat maqsad element massivdagi oxirgi element bo'lsa yoki massivda bo'lmasa sodir bo'ladi. Bu holda, biz butun massivni aylanib o'tishimiz kerak va shuning uchun taqqoslashlar soni N bo'ladi. Demak, vaqt murakkabligi bo'ladi O(N).
Ikkilik qidiruv
Ushbu turdagi qidirish algoritmi tartiblangan massivda joylashgan ma'lum bir qiymatning o'rnini topish uchun ishlatiladi . Ikkilik qidiruv algoritmi bo'lish va zabt etish tamoyili asosida ishlaydi va u eng yaxshi qidiruv algoritmi hisoblanadi, chunki u tezroq ishlaydi.
Keling, misol sifatida tartiblangan massivni olaylik va uning qanday ishlashini tushunishga harakat qilamiz:
arr = [2, 12, 15, 17, 27, 29, 45]
Aytaylik, qidiriladigan maqsad elementi 17.