Binary Search
A binary search algorithm finds the position of the target element in a sorted array. It compares the target element with the middle element of the array.
Binary search exhibits better timing behaviour for large volume of data with timing complexity O(log2n)
Binary search is a search technique that works efficiently on sorted lists.
Binary search uses the divide and conquer strategy, in which the list is divided into two halves, with the item being compared with the middle element of the list.
If a match is found, the location of the middle element is returned. Otherwise, we search into either of the halves depending on the result produced through the match.
Binary Search
#include <stdio.h>
int binary_search(int a[], int beg, int end, int key) {
int mid;
if(end >= beg) {
mid = (beg + end) / 2;
/* if the item to be searched is present at middle */
if(a[mid] == key)
return mid + 1;
/* if the item to be searched is smaller than middle, then it can only be in left sub-array */
else if(a[mid] < key)
return binary_search(a, mid + 1, end, key);
/* if the item to be searched is greater than middle, then it can only be in right sub-array */
else
return binary_search(a, beg, mid - 1, key);
}
return -1;
}
int main() {
// The given array
int a[] = {11, 14, 25, 30, 40, 45, 60, 65, 90};
// The value to be searched
int key = 45;
// The size of array
int n = sizeof(a) / sizeof(a[0]);
// Store the result
int result = binary_search(a, 0, n-1, key);
printf("The elements of the array are - ");
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\nElement to be searched is - %d", key);
if (result != -1)
printf("\nElement is present at %d position of array", result);
else
printf("\nElement is not present in the array");
return 0;
}public class BinarySearch {
static int binarySearch(int a[], int beg, int end, int key) {
int mid;
if(end >= beg) {
mid = (beg + end) / 2;
/* if the item to be searched is present at middle */
if(a[mid] == key)
return mid + 1;
/* if the item to be searched is smaller than middle, then it can only
be in left sub-array */
else if(a[mid] < key)
return binarySearch(a, mid + 1, end, key);
/* if the item to be searched is greater than middle, then it can only be
in right sub-array */
else
return binarySearch(a, beg, mid - 1, key);
}
return -1;
}
public static void main(String args[]) {
// The given array
int a[] = {11, 14, 25, 30, 40, 45, 60, 65, 90};
// The value to be searched
int key = 60;
// The size of array
int n = a.length;
// Store the result
int result = binarySearch(a, 0, n - 1, key);
System.out.print("The elements of the array are: ");
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
System.out.println();
System.out.println("Element to be searched is: " + key);
if (result != -1)
System.out.println("Element is present at " + result + " position of array");
else
System.out.println("Element is not present in the array");
}
}
Time Complexity
| Case | Time Complexity |
|---|---|
| Best Case | O(1) |
| Average Case | O(log n) |
| Worst Case | O(log n) |
- Best Case O(1): It occurs when the element to be search is found in first comparison. That is the first middle element itself is the element to be searched
- Average Case O(log n): Binary search has an average case time complexity of O(log n)
- Worst Case O(log n): The worst case occurs in Binary search when we have to keep reducing the search space until it contains only one element.
The binary search has a time complexity of O(long n)
Space Complexity
The binary search has a space complexity of O(1).