Implementace iterací
int binarySearch(int search, int A[], int n) { int i = 0, j = n - 1, mid; while (i > 1); // found x, return if (A[mid] == search) return mid; // x lies after mid if (A[mid] < search) i = mid + 1; // x lies before mid else j = mid - 1; } return -1; }
Implementace rekurzí
int binarySearch(int search, int A[], int i, int j) { if (i > j) return -1; // (i+j) may overflow int mid = i + ((j-i) >> 1); if (A[mid] == search) return mid; if (A[mid] < search) { return binarySearch(search, A, mid + 1, j); } else { return binarySearch(search, A, i, mid - 1); } }
Složitost
Při hledání v posloupnosti délky n provede algoritmus BinSearch nejvýše log2(n) průchodů cyklem.
DŮKAZ: Stačí nahlédnout, že v každém průchodu cyklem se velikost prohledávaného úseku zmenší alespoň dvakrát. Proto po k průchodech úsek obsahuje nejvýše n/2k prvků, takže pro k > log2 n je úsek nutně prázdný.