Binär sökning

I den här handledningen lär du dig hur Binary Search sorterar. Du hittar också arbetsexempel på binär sökning i C, C ++, Java och Python.

Binär sökning är en sökalgoritm för att hitta ett elements position i en sorterad matris.

I detta tillvägagångssätt söks alltid elementet mitt i en del av en matris.

Binär sökning kan endast genomföras på en sorterad lista med objekt. Om elementen inte redan är sorterade måste vi först sortera dem.

Binär sökning fungerar

Binär sökalgoritm kan implementeras på två sätt som diskuteras nedan.

  1. Iterativ metod
  2. Rekursiv metod

Den rekursiva metoden följer uppdelnings- och erövringsstrategin.

De allmänna stegen för båda metoderna diskuteras nedan.

  1. Matrisen i vilken sökning ska utföras är: Initial array
    Låt x = 4vara det element som ska sökas.
  2. Ställ in två pekare låg och hög på lägsta respektive högsta position. Ställer in pekare
  3. Hitta mittelementet mitt i matrisen, dvs. (arr(low + high)) / 2 = 6. Mittelement
  4. Om x == mitt, återvänd sedan mitt.Else, jämför det element som ska sökas med m.
  5. Om x> mid, jämför x med elementets mittelement på höger sida om mitt. Detta görs genom att ställa in låg till low = mid + 1.
  6. Annars, jämför x med elementets mittelement på vänster sida av mitten. Detta görs genom att sätta högt till high = mid - 1. Hitta mittelement
  7. Upprepa steg 3 till 6 tills lågt möter högt. Mittelement
  8. x = 4är hittad. Hittades

Binär sökalgoritm

Iterationsmetod

gör tills pekarna låga och höga möter varandra. mitt = (lågt + högt) / 2 om (x == arr (mitt)) återvänder mitt annat om (x> A (mitt)) // x är på höger sida lågt = mitt + 1 annat // x är på vänster sida hög = mitt - 1

Rekursiv metod

 binärsökning (arr, x, låg, hög) om låg> hög avkastning Falskt annat mitt = (lågt + högt) / 2 om x == arr (mitt) återvänder mitt annat om x <data (mitt) // x är på höger sida returnera binär Sök (arr, x, mitt + 1, hög) annars // x är på höger sida returnera binär Sök (arr, x, låg, mitt - 1)

Python, Java, C / C ++ exempel (Iterativ metod)

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 ++ exempel (rekursiv metod)

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ökningskomplexitet

Tidskomplexiteter

  • Komplexitet i bästa fall :O(1)
  • Genomsnittlig fallkomplexitet :O(log n)
  • Värsta fallets komplexitet :O(log n)

Rymdkomplexitet

Utrymmets komplexitet i den binära sökningen är O(n).

Binära sökapplikationer

  • I Java-bibliotek, .Net, C ++ STL
  • Under felsökning används den binära sökningen för att hitta den plats där felet inträffar.

Intressanta artiklar...