Binäre Suche
Schreiben Sie bei einem gegebenen sortierten Array arr[] mit n Elementen eine Funktion, um ein gegebenes Element x in arr[] zu suchen.
Ein einfacher Ansatz besteht darin, eine lineare Suche durchzuführen . Die Zeitkomplexität des obigen Algorithmus ist O(n). Ein anderer Ansatz zur Durchführung derselben Aufgabe ist die Verwendung der binären Suche.
Binäre Suche: Durchsuchen Sie ein sortiertes Array, indem Sie das Suchintervall wiederholt halbieren. Beginnen Sie mit einem Intervall, das das gesamte Array abdeckt. Wenn der Wert des Suchschlüssels kleiner als das Element in der Mitte des Intervalls ist, grenzen Sie das Intervall auf die untere Hälfte ein. Andernfalls verengen Sie es auf die obere Hälfte. Wiederholen Sie die Überprüfung, bis der Wert gefunden wurde oder das Intervall leer ist.
Beispiel :
Die Idee der binären Suche besteht darin, die Information zu verwenden, dass das Array sortiert ist, und die Zeitkomplexität auf O (Log n) zu reduzieren.
Wir ignorieren im Grunde die Hälfte der Elemente nach einem Vergleich.
- Vergleiche x mit dem mittleren Element.
- Wenn x mit dem mittleren Element übereinstimmt, geben wir den mittleren Index zurück.
- Else Wenn x größer als das mittlere Element ist, dann kann x nur in der rechten Hälfte des Subarrays nach dem mittleren Element liegen. Also wiederholen wir für die rechte Hälfte.
- Else (x ist kleiner) wiederholen sich für die linke Hälfte.
Rekursive Implementierung der binären Suche
C++
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
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
// C program to implement recursive Binary Search
#include <stdio.h>
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
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
// Java implementation of recursive Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[l..
// r], else return -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the
// middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver method to test above
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, 0, n - 1, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
/* This code is contributed by Rajat Mishra */
Python3
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
# Driver Code
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 % d" % result)
else:
print ("Element is not present in array")
C#
// C# implementation of recursive Binary Search
using System;
class GFG {
// Returns index of x if it is present in
// arr[l..r], else return -1
static int binarySearch(int[] arr, int l,
int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the
// middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver method to test above
public static void Main()
{
int[] arr = { 2, 3, 4, 10, 40 };
int n = arr.Length;
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
Console.WriteLine("Element not present");
else
Console.WriteLine("Element found at index "
+ result);
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to implement
// recursive Binary Search
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r]
// is present, otherwise -1
function binarySearch($arr, $l, $r, $x)
{
if ($r >= $l)
{
$mid = ceil($l + ($r - $l) / 2);
// If the element is present
// at the middle itself
if ($arr[$mid] == $x)
return floor($mid);
// If element is smaller than
// mid, then it can only be
// present in left subarray
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
// Else the element can only
// be present in right subarray
return binarySearch($arr, $mid + 1,
$r, $x);
}
// We reach here when element
// is not present in array
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.
?>
Javascript
<script>
// JavaScript program to implement recursive Binary Search
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, l, r, x){
if (r >= l) {
let mid = l + Math.floor((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length
let result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? document.write( "Element is not present in array")
: document.write("Element is present at index " +result);
</script>
Ausgabe :
Element is present at index 3
Hier können Sie zur einfacheren Implementierung eine Prüffunktion erstellen.
Hier ist eine rekursive Implementierung mit Prüffunktion, die meiner Meinung nach eine viel einfachere Implementierung ist:
C++
#include <bits/stdc++.h>
using namespace std;
//define array globally
const int N = 1e6 +4;
int a[N];
int n;//array size
//elememt to be searched in array
int k;
bool check(int dig)
{
//element at dig position in array
int ele=a[dig];
//if k is less than
//element at dig position
//then we need to bring our higher ending to dig
//and then continue further
if(k<=ele)
{
return 1;
}
else
{
return 0;
}
}
void binsrch(int lo,int hi)
{
while(lo<hi)
{
int mid=(lo+hi)/2;
if(check(mid))
{
hi=mid;
}
else
{
lo=mid+1;
}
}
//if a[lo] is k
if(a[lo]==k)
cout<<"Element found at index "<<lo;// 0 based indexing
else
cout<<"Element doesnt exist in array";//element was not in our array
}
int main()
{
cin>>n;
for(int i=0; i<n; i++)
{
cin>>a[i];
}
cin>>k;
//it is being given array is sorted
//if not then we have to sort it
//minimum possible point where our k can be is starting index
//so lo=0
//also k cannot be outside of array so end point
//hi=n
binsrch(0,n);
return 0;
}
Iterative Implementierung der binären Suche
C++
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
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
// C program to implement iterative Binary Search
#include <stdio.h>
// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
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
// Java implementation of iterative Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[],
// else return -1
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
// Driver method to test above
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 not present");
else
System.out.println("Element found at "
+ "index " + result);
}
}
Python3
# Python3 code to implement iterative Binary
# Search.
# It returns location of x in given array arr
# if present, else returns -1
def binarySearch(arr, l, r, x):
while l <= r:
mid = l + (r - l) // 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:
l = mid + 1
# If x is smaller, ignore right half
else:
r = mid - 1
# If we reach here, then the element
# was not present
return -1
# Driver Code
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 % d" % result)
else:
print ("Element is not present in array")
C#
// C# implementation of iterative Binary Search
using System;
class GFG {
// Returns index of x if it is present in arr[],
// else return -1
static int binarySearch(int[] arr, int x)
{
int l = 0, r = arr.Length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
// Driver method to test above
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 not present");
else
Console.WriteLine("Element found at "
+ "index " + result);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to implement
// iterative Binary Search
// A iterative binary search
// function. It returns location
// of x in given array arr[l..r]
// if present, otherwise -1
function binarySearch($arr, $l,
$r, $x)
{
while ($l <= $r)
{
$m = $l + ($r - $l) / 2;
// Check if x is present at mid
if ($arr[$m] == $x)
return floor($m);
// If x greater, ignore
// left half
if ($arr[$m] < $x)
$l = $m + 1;
// If x is smaller,
// ignore right half
else
$r = $m - 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.
?>
Javascript
<script>
// Program to implement recursive Binary Search
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
function binarySearch(arr, l, r, x)
{
if (r >= l) {
mid = l + Math.floor((r - l) / 2);
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
arr =new Array(2, 3, 4, 10, 40);
x = 10;
n = arr.length;
result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? document.write("Element is not present in array")
: document.write ("Element is present at index " + result);
// This code is contributed by simranarora5sos
</script>
Ausgabe :
Element is present at index 3
Zeitkomplexität:
Die Zeitkomplexität der binären Suche kann geschrieben werden als
T(n) = T(n/2) + c
Die obige Wiederholung kann entweder mit der Recurrence Tree-Methode oder der Master-Methode gelöst werden. Es fällt in Fall II der Master-Methode und die Lösung der Wiederholung ist 
.
Hilfsraum: O(1) bei iterativer Implementierung. Im Fall einer rekursiven Implementierung O(Logn)-Rekursionsaufrufspeicherplatz.
Algorithmisches Paradigma: Verringern und erobern .
Notiz:
Hier verwenden wir
int mid = niedrig + (hoch – niedrig)/2;
Vielleicht fragen Sie sich, warum wir den mittleren Index so berechnen , wir können einfach den unteren und den höheren Index addieren und durch 2 teilen.
int mid = (niedrig + hoch)/2;
Aber wenn wir den mittleren Index so berechnen , bedeutet das, dass unser Code nicht 100% korrekt ist, er enthält Fehler.
Das heißt, es schlägt bei größeren Werten der int-Variablen low und high fehl. Insbesondere schlägt es fehl, wenn die Summe von niedrig und hoch größer als der maximale positive int-Wert ist (2 31 – 1).
Die Summe läuft auf einen negativen Wert über und der Wert bleibt negativ, wenn er durch 2 geteilt wird. In Java wird ArrayIndexOutOfBoundException ausgelöst.
int mid = niedrig + (hoch – niedrig)/2;
Es ist also besser, es so zu verwenden. Dieser Fehler betrifft gleichermaßen Merge-Sort- und andere Divide-and-Conquer-Algorithmen.
Geeksforgeeks-Kurse:
1. Sprachgrundlagenkurse [ C++ / JAVA / Python ]
Lernen Sie jede Programmiersprache von Grund auf und verstehen Sie alle ihre grundlegenden Konzepte für eine starke Programmiergrundlage auf einfachste Weise mit Hilfe der GeeksforGeeks Sprachgrundlagenkurse – Java Foundation | Python-Stiftung | C++-Grundlage
2. Geeks-Kurse Live
Holen Sie sich von jedem geografischen Standort aus interviewzentrierte Live-Online-Kurse zu Datenstruktur und Algorithmen, um DSA-Konzepte zu lernen und zu beherrschen, um Ihre Problemlösungs- und Programmierfähigkeiten zu verbessern und das Interview mit jedem produktbasierten Unternehmen zu knacken – Geeks-Kurse : Live-Sitzung
3. Vollständige Vorbereitung
auf Vorstellungsgespräche Erfüllen Sie alle Ihre Anforderungen an die Vorbereitung auf Vorstellungsgespräche an einem einzigen Ort mit dem Kurs zur vollständigen Vorbereitung auf Vorstellungsgespräche , der Ihnen alle erforderlichen Dinge zur Vorbereitung auf jedes produktbasierte, dienstleistungsbasierte oder Start-up-Unternehmen zum günstigsten Preis bietet Preise.
4. DSA Self Paced
Beginnen Sie mit dem Erlernen von Datenstrukturen und Algorithmen, um sich auf die Interviews mit Top-IT-Giganten wie Microsoft, Amazon, Adobe usw. vorzubereiten das auch in Ihrem eigenen Tempo und Komfort.
5. Unternehmensspezifische Kurse – Amazon , Microsoft , TCS & Wipro
Knacken Sie das Vorstellungsgespräch eines produktbasierten Riesenunternehmens, indem Sie sich speziell auf die Fragen vorbereiten, die diese Unternehmen normalerweise in ihrer Kodierungs-Interviewrunde stellen. Siehe unternehmensspezifische GeeksforGeeks-Kurse: Amazon SDE-Testreihe usw.
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .