Binārā meklēšana

Šajā apmācībā jūs uzzināsiet, kā darbojas binārā meklēšana. Jūs atradīsit arī binārā meklēšanas piemērus C, C ++, Java un Python.

Binārā meklēšana ir meklēšanas algoritms, lai atrastu elementa pozīciju sakārtotā masīvā.

Šajā pieejā elements vienmēr tiek meklēts masīva daļas vidū.

Bināro meklēšanu var ieviest tikai sakārtotā vienumu sarakstā. Ja elementi jau nav kārtoti, mums tie vispirms ir jāšķiro.

Binārā meklēšana darbojas

Binārās meklēšanas algoritmu var ieviest divos veidos, kas tiek apspriesti turpmāk.

  1. Iteratīvā metode
  2. Rekursīvā metode

Rekurzīvajā metodē tiek izmantota sadalīšanas un iekarošanas pieeja.

Abu metožu vispārīgie soļi ir aplūkoti turpmāk.

  1. Masīvs, kurā jāveic meklēšana, ir: Sākotnējais masīvs
    Let x = 4ir meklējamais elements.
  2. Iestatiet divus rādītājus zemu un augstu attiecīgi zemākajā un augstākajā pozīcijā. Norāžu iestatīšana
  3. Atrodiet vidējo elementu masīva vidū, ti. (arr(low + high)) / 2 = 6. Vidus elements
  4. Ja x == vidū, tad atgriezieties vidū. Vēl salīdziniet meklējamo elementu ar m.
  5. Ja x> mid, salīdziniet x ar elementu vidējo elementu vidusdaļas labajā pusē. Tas tiek darīts, iestatot zemu uz low = mid + 1.
  6. Citādi salīdziniet x ar elementu vidējo elementu vidusdaļas kreisajā pusē. Tas tiek darīts, iestatot augstu uz high = mid - 1. Vidus elementa atrašana
  7. Atkārtojiet 3. līdz 6. darbību, līdz zems sasniedz augstu. Vidus elements
  8. x = 4ir atrasts. Atrasts

Binārās meklēšanas algoritms

Iterācijas metode

dariet līdz brīdim, kad zemie un augstie rādītāji satiekas. vidus = (zems + augsts) / 2, ja (x == arr (vidus)) atgriežas vidū, ja (x> A (vidus)) // x atrodas labajā pusē zems = vidus + 1 cits // x ir ieslēgts kreisā puse augsta = vidus - 1

Rekursīvā metode

 binārā meklēšana (arr, x, zema, augsta), ja zema> augsta atdeve Nepareiza cita vidus = (zema + augsta) / 2, ja x == arr (vidēja) atgriežas citā vietā, ja x <dati (vidū) // x ir labajā pusē atgriezties binārā meklēšana (arr, x, vidus + 1, augsts) cits // x ir labajā pusē atgriež bināro meklēšanu (arr, x, zems, vidū - 1)

Python, Java, C / C ++ piemēri (atkārtojošā metode)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): # Repeat until the pointers low and high meet each other while low <= high: mid = low + (high - low)//2 if array(mid) == x: return mid elif array(mid) < x: low = mid + 1 else: high = mid - 1 return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); return 0; )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( // Repeat until the pointers low and high meet each other while (low <= high) ( int mid = low + (high - low) / 2; if (array(mid) == x) return mid; if (array(mid) < x) low = mid + 1; else high = mid - 1; ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Python, Java, C / C ++ piemēri (rekursīvā metode)

Python Java C C ++ 
 # Binary Search in python def binarySearch(array, x, low, high): if high>= low: mid = low + (high - low)//2 # If found at mid, then return it if array(mid) == x: return mid # Search the left half elif array(mid)> x: return binarySearch(array, x, low, mid-1) # Search the right half else: return binarySearch(array, x, mid + 1, high) else: return -1 array = (3, 4, 5, 6, 7, 8, 9) x = 4 result = binarySearch(array, x, 0, len(array)-1) if result != -1: print("Element is present at index " + str(result)) else: print("Not found")
 // Binary Search in Java class BinarySearch ( int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) public static void main(String args()) ( BinarySearch ob = new BinarySearch(); int array() = ( 3, 4, 5, 6, 7, 8, 9 ); int n = array.length; int x = 4; int result = ob.binarySearch(array, x, 0, n - 1); if (result == -1) System.out.println("Not found"); else System.out.println("Element found at index " + result); ) )
 // Binary Search in C #include int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int n = sizeof(array) / sizeof(array(0)); int x = 4; int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )
 // Binary Search in C++ #include using namespace std; int binarySearch(int array(), int x, int low, int high) ( if (high>= low) ( int mid = low + (high - low) / 2; // If found at mid, then return it if (array(mid) == x) return mid; // Search the left half if (array(mid)> x) return binarySearch(array, x, low, mid - 1); // Search the right half return binarySearch(array, x, mid + 1, high); ) return -1; ) int main(void) ( int array() = (3, 4, 5, 6, 7, 8, 9); int x = 4; int n = sizeof(array) / sizeof(array(0)); int result = binarySearch(array, x, 0, n - 1); if (result == -1) printf("Not found"); else printf("Element is found at index %d", result); )

Binārā meklēšanas sarežģītība

Laika sarežģītība

  • Labākā gadījuma sarežģītība :O(1)
  • Vidējā lietu sarežģītība :O(log n)
  • Sliktākā gadījuma sarežģītība :O(log n)

Kosmosa sarežģītība

Binārā meklēšanas telpas sarežģītība ir O(n).

Binārās meklēšanas programmas

  • Java, .Net, C ++ STL bibliotēkās
  • Atkļūdošanas laikā binārā meklēšana tiek izmantota, lai precīzi noteiktu vietu, kur notiek kļūda.

Interesanti raksti...