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

Ikkilik qidiruvga yondashuv

• 
  Maqsadli elementni massivning o'rta elementi bilan solishtiring.
  
• 
  Agar maqsad element o'rta elementdan kattaroq bo'lsa, qidiruv o'ng yarmida davom etadi.
  
• 
  Agar maqsad element o'rta qiymatdan kichik bo'lsa, qidiruv chap yarmida davom etadi.
  
• 
  Bu jarayon o'rta element maqsad elementga teng bo'lguncha yoki maqsad element massivda bo'lmaguncha takrorlanadi
  
• 
  Agar maqsad element topilsa, uning indeksi qaytariladi, aks holda -1 qaytariladi.
  

Kodni amalga oshirish
Java-da ikkilik qidiruv
package algorithms.searching;


public class BinarySearch {
public static void main(String[] args) {
int[] nums = {2, 12, 15, 17, 27, 29, 45};
int target = 17;
System.out.println(search(nums, target));
}


static int search(int[] nums, int target) {
int start = 0;
int end = nums.length - 1;


while (start <= end) {
int mid = start + (end - start) / 2;


if (nums[mid] > target)
end = mid - 1;
else if (nums[mid] < target)
start = mid + 1;
else
return mid;
}
return -1;
}
}
Pythonda ikkilik qidiruv
def search(nums, target):
start = 0
end = len(nums)-1


while start <= end:
mid = start + (end-start)//2
if nums[mid] > target:
end = mid-1
elif nums[mid] < target:
start = mid+1
else:
return mid


return -1
if __name__ == '__main__':
nums = [2, 12, 15, 17, 27, 29, 45]
target = 17
print(search(nums, target))
Vaqt murakkabligi tahlili
Eng yaxshi holat maqsad element massivning o'rta elementi bo'lganda yuzaga keladi. Taqqoslashlar soni, bu holda, 1. Demak, vaqt murakkabligi O(1).