Binært søk

I denne veiledningen vil du lære hvordan Binary Search-sortering fungerer. Du finner også arbeidseksempler på Binary Search i C, C ++, Java og Python.

Binær søk er en søkealgoritme for å finne et elementets posisjon i en sortert matrise.

I denne tilnærmingen blir elementet alltid søkt midt i en del av en matrise.

Binært søk kan bare implementeres på en sortert liste over varer. Hvis elementene ikke allerede er sortert, må vi først sortere dem.

Binær søk fungerer

Binær søkealgoritme kan implementeres på to måter som er diskutert nedenfor.

  1. Iterativ metode
  2. Rekursiv metode

Den rekursive metoden følger skillet og erobre tilnærmingen.

De generelle trinnene for begge metodene er diskutert nedenfor.

  1. Matrisen der søking skal utføres er: Initial array
    La x = 4være elementet som skal søkes.
  2. Sett to pekere på henholdsvis laveste og høyeste plassering. Setter pekere
  3. Finn midtelementet midt i matrisen, dvs. (arr(low + high)) / 2 = 6. Midt element
  4. Hvis x == mid, returner deretter mid.Else, sammenlign elementet som skal søkes med m.
  5. Hvis x> mid, sammenlign x med midtelementet til elementene på høyre side av midten. Dette gjøres ved å sette lavt til low = mid + 1.
  6. Ellers, sammenlign x med midtelementet til elementene på venstre side av midten. Dette gjøres ved å sette høyt til high = mid - 1. Finne midtelement
  7. Gjenta trinn 3 til 6 til lav møter høy. Midt element
  8. x = 4er funnet. Funnet

Binær søkealgoritme

Iterasjonsmetode

gjør til pekerne lave og høye møter hverandre. midt = (lav + høy) / 2 hvis (x == arr (midt)) returnerer midt annet hvis (x> A (midt)) // x er på høyre side lav = midt + 1 annet // x er på venstre side høy = midt - 1

Rekursiv metode

 binærsøk (arr, x, lav, høy) hvis lav> høy retur Falsk annet midt = (lav + høy) / 2 hvis x == arr (midt) retur midt annet hvis x <data (midt) // x er på høyre side return binærsøk (arr, x, midt + 1, høy) ellers // x er på høyre side return binær søk (arr, x, lav, midt - 1)

Python, Java, C / C ++ eksempler (Iterativ 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 ++ eksempler (rekursiv 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 søkekompleksitet

Tidskompleksiteter

  • Beste tilfelle kompleksitet :O(1)
  • Gjennomsnittlig sakskompleksitet :O(log n)
  • Kompleksitet i verste fall :O(log n)

Romkompleksitet

Romkompleksiteten til det binære søket er O(n).

Binære søkeapplikasjoner

  • I biblioteker på Java, .Net, C ++ STL
  • Under feilsøking brukes binært søk for å finne stedet der feilen oppstår.

Interessante artikler...