Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714631

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

Binar qidirish(Binary_search)O(log n)

 

Binar qidiruv o’sish bo’yicha saralangan massivdan biz qidirgan sonni topishda ishlatiladi. Masalan a{1,2,5,8,9,12} berilgan massivdan 9 sonini oddiy qidiruvda ishlash vaqti O(n) bo’ladi. Lekin agar siz binary qidirishni ishlatsangiz ishlash vaqti ancha tezlashadi yani O(log n) bo’ladi. Endi siz bilan binar qidirish algoritmini g’oyasini ko’rib chiqamiz. Binary qidirish massivni ikkiga bo’lish orqali qidiradi yani left va right bo’lgan ikki o’zgaruvchi olinadi dastlab left=1 va right=n  bo’ladi va left va right qo’shib ikkiga bo’ladi(middle=(left+right)/2) shunda massiv o’rtasidagi element(middle) topiladi va tekshiriladi shu element biz qidiryotgan elementga tengmi agar teng bo’lsa shu element turgan index javob qilib yuboriladi aks xolda shart tekshiriladi biz qidiryotgan element (find) middle elementdan kattami (a[middle]<find) agar katta bo’lsa unda biz qidiryotgan elementimiz massivni o’ng tomonida yani middle+1 va right orasida bo’ladi aks xolda chap tomonida yani

left va middle-1 orasida bo’ladi va shu tariqa ikkiga bo’lib qidirib borilaveradi. Masalan:    a{1,2,5,8,9,12,34} shu massivdan 9 ni qidirib ko’raylik. Demak

1.left=1 va right=7                 middle=(left+right)/2=4          a[middle]≠9; topilmadi

endi shart tekshiramiz a[middle]<9 bajariladi demak 9 o’ng tomonda demak

left=middle+1 bo’ladi right esa o’zgarmaydi. O’ng tomonda {9,12,34}

 

2.left=5 va right=7                 middle=(left+right)/2=6          a[middle]≠9; topilmadi

endi shart tekshiramiz a[middle]<9 bajarilmayadi demak 9 chap tomonda ekan demak left o’zgarmaydi right esa right=middle-1 bo’ladi.

3.left=5 va right=5                 middle=(left+right)/2=5          a[middle]=9;topildi demak javob middle=5 ekan.

 

 

 

Masalan: . qidir 114  a{-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}. Jadvalda ko’ramiz.

qadam 1(middle element 19<114):-1 5 6 18 19 25 46 78 102 114

qadam 2(middle element 78<114):-1 5 6 18 19 25 46 78 102 114

qadam 3(middle element 102<114):-1 5 6 18 19 25 46 78 102 114

qadam 4 (middle element 114=114):-1 5 6 18 19 25 46 78  102 114

Masalan. qidir 6  a{-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}

qadam 1 (middle element 19>6):-1 5 6 18 19 25 46 78 102 114

qadam 2 (middle element 5<6):-1 5 6 18 19 25 46 78 102 114

qadam 3 (middle element 6=6):-1 5 6 18 19 25 46 78 102 114

Endi realizatsiyani ko’rib chiqamiz Pascal tilida:

 

var

     a:array[1..1000000] of integer;

     n,find,left,right,middle,i:integer;

     begin

        read(n);

          for i:=1 to n do

              read(a[i]);

              read(find);

              left:=1;  right:=n;

                 while(left<=right)do

                        begin

                        middle:=trunc((left+right)/2);

                        if(a[middle]=find) then

                          begin

                            write(middle);

                            exit;

                          end;

                        if(a[middle]<find) then

                              left:=middle+1

                              else

                              right:=middle-1;

                        end;

                          write('Bunday son topilmadi');

     end.

 

 

Java tilida xam shunday bo’ladi Lekin Java va C++ tillarida Binary_searchni tayyor funksiyasi mavjud shuni javada ko’rib chiqamiz.

 

 

import java.util.Arrays;

import java.util.Scanner;

public class SEARCH_BINARY {

public static void main(String[] args) {

     Scanner sc = new Scanner(System.in);

     int n=sc.nextInt();

     int a[]=new int[n+1];

     for (int i = 1; i <=n; i++) {

         a[i]=sc.nextInt();

     }

     int find=sc.nextInt();

     int index=Arrays.binarySearch(a, find);

     System.out.println(index);

}

 

                              C++ tilidagi funksiyasi

 

int binarySearch(int arr[], int value, int left, int right) {

      while (left <= right) {

            int middle = (left + right) / 2;

            if (arr[middle] == value)

                  return middle;

            else if (arr[middle] > value)

                  right = middle - 1;

            else

                  left = middle + 1;

      }

      return -1;

}

 

 

 

 

 

 

Ro`yxatga qaytish        Muallifi: Bahrom Sultonov