Binær søgning

I denne vejledning lærer du, hvordan sortering af binær søgning fungerer. Du finder også arbejdseksempler på binær søgning i C, C ++, Java og Python.

Binær søgning er en søgealgoritme til at finde et elements position i et sorteret array.

I denne tilgang søges elementet altid midt i en del af et array.

Binær søgning kan kun implementeres på en sorteret liste over varer. Hvis elementerne ikke allerede er sorteret, skal vi først sortere dem.

Binær søgning fungerer

Binær søgealgoritme kan implementeres på to måder, som diskuteres nedenfor.

  1. Iterativ metode
  2. Rekursiv metode

Den rekursive metode følger divide and conquer tilgangen.

De generelle trin for begge metoder diskuteres nedenfor.

  1. Det array, hvor søgning skal udføres, er: Initial array
    Lad x = 4det element, der skal søges i.
  2. Sæt to markører lavt og højt på henholdsvis den laveste og den højeste position. Indstilling af markører
  3. Find det midterste element midt i arrayet, dvs. (arr(low + high)) / 2 = 6. Midt element
  4. Hvis x == midt, så vend tilbage midt.Else, sammenlign det element, der skal søges med m.
  5. Hvis x> mid, sammenlign x med elementernes midterste element på højre side af midten. Dette gøres ved at indstille lav til low = mid + 1.
  6. Ellers sammenligner du x med det midterste element af elementerne på venstre side af midten. Dette gøres ved at indstille højt til high = mid - 1. Find midt element
  7. Gentag trin 3 til 6, indtil lavt møder højt. Midt element
  8. x = 4er fundet. Fundet

Binær søgealgoritme

Iterationsmetode

gør indtil pointerne lave og høje møder hinanden. midt = (lav + høj) / 2 hvis (x == arr (midt)) vender tilbage ellers hvis (x> A (midt)) // x er på højre side lav = midt + 1 andet // x er på venstre side høj = midt - 1

Rekursiv metode

 binærsøgning (arr, x, lav, høj) hvis lav> høj retur Falsk andet midt = (lav + høj) / 2 hvis x == arr (midt) returnerer midt ellers hvis x <data (midt) // x er på højre side return binærsøgning (arr, x, midt + 1, høj) ellers // x er på højre side return binær søgning (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øgningskompleksitet

Tidskompleksiteter

  • Kompleksitet i bedste tilfælde :O(1)
  • Gennemsnitlig sags kompleksitet :O(log n)
  • Værste tilfælde kompleksitet :O(log n)

Rumkompleksitet

Rumkompleksiteten af ​​den binære søgning er O(n).

Binære søgeapplikationer

  • I Java-biblioteker, .Net, C ++ STL
  • Under fejlretning bruges binær søgning til at lokalisere det sted, hvor fejlen opstår.

Interessante artikler...