// C++ program to implement iterative Binary Search #include  using namespace std; // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  int result = binarySearch(arr, 0, n - 1, x);  (result == -1)  ? cout << 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>

// C program to implement iterative Binary Search #include  // An iterative binary search function. int binarySearch(int arr[], int low, int high, int x) {  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was not present  return -1; } // Driver code int main(void) {  int arr[] = { 2, 3, 4, 10, 40 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 10;  int result = binarySearch(arr, 0, n - 1, x);  (result == -1) ? printf('Element is not present'  ' in array')  : printf('Element is present at '  'index %d',  result);  return 0; }>

// Java implementation of iterative Binary Search import java.io.*; class BinarySearch {    // Returns index of x if it is present in arr[].  int binarySearch(int arr[], int x)  {  int low = 0, high = arr.length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void main(String args[])  {  BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.length;  int x = 10;  int result = ob.binarySearch(arr, x);  if (result == -1)  System.out.println(  'Element is not present in array');  else  System.out.println('Element is present at '  + 'index ' + result);  } }>

# Python3 code to implement iterative Binary # Search. # It returns location of x in given array arr def binarySearch(arr, low, high, x): while low <= high: mid = low + (high - low) // 2 # Check if x is present at mid if arr[mid] == x: return mid # If x is greater, ignore left half elif arr[mid] < x: low = mid + 1 # If x is smaller, ignore right half else: high = mid - 1 # If we reach here, then the element # was not present return -1 # Driver Code if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Function call result = binarySearch(arr, 0, len(arr)-1, x) if result != -1: print('Element is present at index', result) else: print('Element is not present in array')>

// C# implementation of iterative Binary Search using System; class GFG {    // Returns index of x if it is present in arr[]  static int binarySearch(int[] arr, int x)  {  int low = 0, high = arr.Length - 1;  while (low <= high) {  int mid = low + (high - low) / 2;  // Check if x is present at mid  if (arr[mid] == x)  return mid;  // If x greater, ignore left half  if (arr[mid] < x)  low = mid + 1;  // If x is smaller, ignore right half  else  high = mid - 1;  }  // If we reach here, then element was  // not present  return -1;  }  // Driver code  public static void Main()  {  int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Length;  int x = 10;  int result = binarySearch(arr, x);  if (result == -1)  Console.WriteLine(  'Element is not present in array');  else  Console.WriteLine('Element is present at '  + 'index ' + result);  } }>

// Program to implement iterative Binary Search   // A iterative binary search function. It returns // location of x in given array arr[l..r] is present, // otherwise -1  function binarySearch(arr, x) {   let low = 0;  let high = arr.length - 1;  let mid;  while (high>= žemas) { mid = žemas + Math.floor((aukštas - žemas) / 2);    // Jei elementas yra viduryje // pats if (arr[mid] == x) return mid;    // Jei elementas yra mažesnis už vidurį, tai // jis gali būti tik kairiajame pogrupyje, jei (arr[mid]> x) high = mid - 1;    // Kitu atveju elementas gali būti tik // dešiniajame pogrupyje else low = mid + 1;  } // Pasiekiame čia, kai elemento nėra // masyve return -1; } arr =naujas Masyvas(2, 3, 4, 10, 40);  x = 10;  n = arr.ilgis;  rezultatas = binarySearch(arr, x);   (rezultatas == -1) ? console.log('Elemento nėra masyve') : console.log ('Elementas yra indekse ' + rezultatas);   // Šį kodą sukūrė simranarora5sos ir rshuklabbb>

 // PHP program to implement // iterative Binary Search // An iterative binary search  // function function binarySearch($arr, $low, $high, $x) { while ($low <= $high) { $mid = $low + ($high - $low) / 2; // Check if x is present at mid if ($arr[$mid] == $x) return floor($mid); // If x greater, ignore // left half if ($arr[$mid] < $x) $low = $mid + 1; // If x is smaller,  // ignore right half else $high = $mid - 1; } // If we reach here, then  // element was not present return -1; } // Driver Code $arr = array(2, 3, 4, 10, 40); $n = count($arr); $x = 10; $result = binarySearch($arr, 0, $n - 1, $x); if(($result == -1)) echo 'Element is not present in array'; else echo 'Element is present at index ', $result; // This code is contributed by anuj_67. ?>>>  
  Išvestis      Laiko sudėtingumas:    O(log N)  
    Pagalbinė erdvė:    O(1)
 
    Rekursyvus dvejetainis paieškos algoritmas:    
 
Sukurkite rekursinę funkciją ir palyginkite paieškos erdvės vidurį su klavišu. Ir pagal rezultatą grąžinkite indeksą, kuriame rastas raktas, arba iškvieskite rekursinę funkciją kitai paieškos vietai.
kas yra uri
 
Rekursinės dvejetainės paieškos algoritmo įgyvendinimas:
C++ 
#include  using namespace std; // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= žemas) { int mid = žemas + (aukštas - žemas) / 2;  // Jei elementas yra viduryje // pats if (arr[mid] == x) return mid;  // Jei elementas yra mažesnis nei mid, tai // jis gali būti tik kairiajame pogrupyje, jei (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Kitu atveju elementas gali būti tik // dešinėje posistemėje return binarySearch(arr, mid + 1, high, x);  } } // Tvarkyklės kodas int main() { int arr[] = { 2, 3, 4, 10, 40 };  int užklausa = 10;  int n = dydis(arr) / dydis(arr[0]);  int rezultatas = binarySearch(arr, 0, n - 1, query);  (rezultatas == -1) ? cout<< 'Element is not present in array'  : cout << 'Element is present at index ' << result;  return 0; }>
 C 
// C program to implement recursive Binary Search #include  // A recursive binary search function. It returns // location of x in given array arr[low..high] is present, // otherwise -1 int binarySearch(int arr[], int low, int high, int x) {  if (high>= žemas) { int mid = žemas + (aukštas - žemas) / 2;  // Jei elementas yra viduryje // pats if (arr[mid] == x) return mid;  // Jei elementas yra mažesnis nei mid, tai // jis gali būti tik kairiajame pogrupyje, jei (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Kitu atveju elementas gali būti tik // dešinėje posistemėje return binarySearch(arr, mid + 1, high, x);  } // Pasiekiame čia, kai elemento nėra // masyve return -1; } // Tvarkyklės kodas int main() { int arr[] = { 2, 3, 4, 10, 40 };  int n = dydis(arr) / dydis(arr[0]);  int x = 10;  int rezultatas = binarySearch(arr, 0, n - 1, x);  (rezultatas == -1) ? printf('Elemento nėra masyve') : printf('Elementas yra indekse %d', rezultatas);  grąžinti 0; }>
 Java 
// Java implementation of recursive Binary Search class BinarySearch {  // Returns index of x if it is present in arr[low..  // high], else return -1  int binarySearch(int arr[], int low, int high, int x)  {  if (high>= žemas) { int mid = žemas + (aukštas - žemas) / 2;  // Jei elementas yra pačiame // viduryje if (arr[mid] == x) return mid;  // Jei elementas yra mažesnis nei mid, tai // jis gali būti tik kairiajame pogrupyje, jei (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Kitu atveju elementas gali būti tik // dešinėje posistemėje return binarySearch(arr, mid + 1, high, x);  } // Čia pasiekiame, kai elemento nėra // masyve return -1;  } // Tvarkyklės kodas public static void main(String args[]) { BinarySearch ob = new BinarySearch();  int arr[] = { 2, 3, 4, 10, 40 };  int n = arr.ilgis;  int x = 10;  int rezultatas = ob.binarySearch(arr, 0, n - 1, x);  if (rezultatas == -1) System.out.println( 'Elemento nėra masyve');  else System.out.println( 'Elementas yra indekse ' + rezultatas);  } } /* Šį kodą sukūrė Rajat Mishra */>
 Python 
# Python3 Program for recursive binary search. # Returns index of x in arr if present, else -1 def binarySearch(arr, low, high, x): # Check base case if high>= žemas: vidutinis = žemas + (aukštas - žemas) // 2 # Jei elementas yra pačiame viduryje if arr[mid] == x: return mid # Jei elementas yra mažesnis už vidurį, tada jis # gali būti tik kairiajame pogrupyje elif arr[mid]> x: return binarySearch(arr, low, mid-1, x) # Kitu atveju elementas gali būti tik # dešiniajame poskirsnyje else: return binarySearch(arr, mid + 1, high, x ) # Elemento masyve nėra: return -1 # Tvarkyklės kodas if __name__ == '__main__': arr = [2, 3, 4, 10, 40] x = 10 # Funkcijos iškvietimo rezultatas = binarySearch( arr, 0, len(arr)-1, x) jei rezultatas != -1: print('Elementas yra indekse', rezultatas) else: print('Elemento nėra masyve')> 
 C# 
// C# implementation of recursive Binary Search using System; class GFG {  // Returns index of x if it is present in  // arr[low..high], else return -1  static int binarySearch(int[] arr, int low, int high, int x)  {  if (high>= žemas) { int mid = žemas + (aukštas - žemas) / 2;  // Jei elementas yra pačiame // viduryje if (arr[mid] == x) return mid;  // Jei elementas yra mažesnis nei mid, tai // jis gali būti tik kairiajame pogrupyje, jei (arr[mid]> x) return binarySearch(arr, low, mid - 1, x);  // Kitu atveju elementas gali būti tik // dešinėje posistemėje return binarySearch(arr, mid + 1, high, x);  } // Čia pasiekiame, kai elemento nėra // masyve return -1;  } // Tvarkyklės kodas public static void Main() { int[] arr = { 2, 3, 4, 10, 40 };  int n = arr.Ilgis;  int x = 10;  int rezultatas = binarySearch(arr, 0, n - 1, x);  if (rezultatas == -1) Console.WriteLine( 'Elemento nėra arrau');  else Console.WriteLine('Elementas yra indekse ' + rezultatas);  } } // Šį kodą pateikė Sam007.>>Javascript>PHP>>  
  Išvestis    Dvejetainės paieškos algoritmo sudėtingumo analizė:  
    Laiko sudėtingumas:     
Geriausias atvejis: O(1)
Vidutinis atvejis: O (log N)
Blogiausias atvejis: O (log N)
    Pagalbinė erdvė:    O(1), jei atsižvelgiama į rekursyvų skambučių krūvą, pagalbinė erdvė bus O(logN).
     Dvejetainės paieškos algoritmo programos:     
Dvejetainė paieška gali būti naudojama kaip sudėtingesnių algoritmų, naudojamų mašininiame mokyme, kūrimo blokas, pavyzdžiui, neuroninių tinklų mokymo algoritmai arba optimalių modelio hiperparametrų paieška.
Jis gali būti naudojamas ieškant kompiuterinėje grafikoje, pvz., spindulių sekimo ar tekstūros atvaizdavimo algoritmuose.
Jis gali būti naudojamas ieškant duomenų bazėje.
    Dvejetainės paieškos pranašumai:    
Dvejetainė paieška yra greitesnė nei tiesinė paieška, ypač didelių masyvų atveju.
Veiksmingesnis nei kiti paieškos algoritmai, kurių laiko sudėtingumas panašus, pvz., interpoliacinė paieška arba eksponentinė paieška.
Dvejetainė paieška puikiai tinka ieškant didelių duomenų rinkinių, saugomų išorinėje atmintyje, pvz., standžiajame diske arba debesyje.
    Dvejetainės paieškos trūkumai:    
Masyvas turi būti surūšiuotas.
Dvejetainė paieška reikalauja, kad ieškoma duomenų struktūra būtų saugoma gretimose atminties vietose.
Dvejetainei paieškai reikia, kad masyvo elementai būtų palyginami, o tai reiškia, kad juos turi būti galima rūšiuoti.
Dažniausiai užduodami klausimai (DUK) dvejetainėje paieškoje:
1. Kas yra dvejetainė paieška?
 
Dvejetainė paieška yra efektyvus algoritmas norint rasti tikslinę vertę surūšiuotame masyve. Jis veikia pakartotinai dalijant paieškos intervalą per pusę.
 
2. Kaip veikia dvejetainė paieška?
 
Dvejetainė paieška lygina tikslinę reikšmę su viduriniu masyvo elementu. Jei jie yra vienodi, paieška sėkminga. Jei tikslas yra mažesnis už vidurinį elementą, paieška tęsiama apatinėje masyvo pusėje. Jei tikslas yra didesnis, paieška tęsiama viršutinėje pusėje. Šis procesas kartojamas tol, kol bus rastas tikslas arba paieškos intervalas tuščias.
 
3. Koks yra dvejetainės paieškos laiko sudėtingumas?
 
Dvejetainės paieškos laiko sudėtingumas yra O(log2n), kur n yra elementų skaičius masyve. Taip yra todėl, kad kiekviename žingsnyje paieškos intervalo dydis sumažinamas perpus.
 
4. Kokios yra dvejetainės paieškos sąlygos?
 
Dvejetainei paieškai reikia, kad masyvas būtų rūšiuojamas didėjančia arba mažėjančia tvarka. Jei masyvas nesurūšiuotas, negalime naudoti dvejetainės paieškos, kad galėtume ieškoti elemento masyve.
 
5. Kas atsitiks, jei masyvas nebus surūšiuotas dvejetainei paieškai?
 
Jei masyvas nesurūšiuotas, dvejetainė paieška gali pateikti neteisingus rezultatus. Jis remiasi rūšiuotu masyvo pobūdžiu, kad priimtų sprendimus, kurioje masyvo pusėje ieškoti.
 
6. Ar dvejetainė paieška gali būti taikoma ne skaitmeniniams duomenims?
 
Taip, dvejetainė paieška gali būti taikoma ne skaitmeniniams duomenims, jei yra nustatyta elementų tvarka. Pavyzdžiui, jis gali būti naudojamas ieškant eilučių abėcėlės tvarka.
 
7. Kokie yra bendri dvejetainės paieškos trūkumai?
 
Dvejetainės paieškos trūkumas yra tas, kad įvesties masyvą reikia rūšiuoti, kad būtų nuspręsta, kurioje pusėje gali būti tikslinis elementas. Todėl nerūšiuotiems masyvams prieš taikydami dvejetainę paiešką turime surūšiuoti masyvą.
 
8. Kada reikėtų naudoti dvejetainę paiešką?
 
Dvejetainė paieška turėtų būti naudojama ieškant tikslinės reikšmės surūšiuotame masyve, ypač kai masyvo dydis yra didelis. Tai ypač efektyvu dideliems duomenų rinkiniams, palyginti su linijiniais paieškos algoritmais.
 
9. Ar dvejetainė paieška gali būti įgyvendinta rekursyviai?
 
Taip, dvejetainę paiešką galima įgyvendinti tiek iteratyviai, tiek rekursyviai. Rekursyvus diegimas dažnai lemia glaustesnį kodą, bet gali turėti šiek tiek daugiau pridėtinių išlaidų dėl rekursinių kamino erdvės arba funkcijų iškvietimų.
 
10. Ar dvejetainė paieška visada yra geriausias pasirinkimas ieškant surūšiuotame masyve?
 
Nors dvejetainė paieška yra labai efektyvi ieškant surūšiuotuose masyvuose, gali būti konkrečių atvejų, kai kiti paieškos algoritmai yra tinkamesni, pavyzdžiui, kai dirbama su mažais duomenų rinkiniais arba kai masyvas dažnai keičiamas.
 
    Susiję straipsniai:     
 
 Dvejetainė paieška atsakymų su problemomis pamoka 
 Linijinė paieška vs dvejetainė paieška 
 Kaip nustatyti ir išspręsti dvejetainės paieškos problemas?