Binary Search
- Searching is the process of finding a particular value or key value in a set of values.
- There are two types of searching:
- Linear Search
- Binary Search algorithm uses the concept of the divide and conquer method. Every iteration, the input array size is reduced by half.
- Binary Search precondition: The input array elements must be in sorted order. This approach divides the array into two halves by finding the middle element. The array before the middle element is called the first half of the array, and the array after the middle element is called the second half of the array.
- Algorithm outcomes – Two results:
- Search key present
- Search key not present
Video Lecture
Binary Search Operation
Basic Operation is Comparison. Find the middle element and divide the array into two halves. mid = (low + high) / 2
There are three cases:
- a) If
key == A[mid]then the key is found at locationmid. Terminate the algorithm. - b) Else if
key > A[mid], then the key may be in the second half. Because the input array is in sorted order, the key may not be in the first half. - c) Else if
key < A[mid], then the key may be in the first half. Because the input array is in sorted order, the key may not be in the second half.
Algorithm
BinarySearch(A[0]..A[n-1], K)
Input: Sorted Array A contains n elements & Search Key K.
Output: If search key K is present, return the index mid; if not present, return -1.
Step 1: Start.
Step 2: Assign low = 0 and high = n-1.
Step 3: Find the mid = (low + high) / 2. mid divides the array into two parts.
Step 4: Compare A[mid] with K.
Step 5: If A[mid] == K, then output the mid as the location of search key and stop the algorithm.
Step 6: If K > A[mid], then take the second half for the next iteration. Go to Step 3.
Step 7: If K < A[mid], then take the first half for the next iteration. Go to Step 3.
Step 8: Output -1.
Step 9: Stop.
Binary Search Code
#include <stdio.h>
int binarySearch(int array[], int key, 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] == key)
return mid;
if (array[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
void InputArray(int A[], int n)
{
int i;
printf("Enter the %d Elements\n",n);
for (i = 0; i < n; i++)
{
scanf("%d",&A[i]);
}
}
// Driver Code
int main(void) {
int array[100],n,key,i;
printf("Enter the size of the array \n");
scanf("%d",&n);
// Function call to input array
InputArray(array,n);
printf("\n Enter Search key value\n");
scanf("%d",&key);
int result = binarySearch(array, key, 0, n - 1);
if (result == -1)
printf("Not found");
else
printf("Element is found at index %d", result);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int binarySearch(const vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid; // Target found at index mid
if (arr[mid] < target)
left = mid + 1; // Target is in the right half
else
right = mid - 1; // Target is in the left half
}
return -1; // Target not found
}
int main() {
vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int result = binarySearch(arr, target);
if (result != -1)
cout < "Element found at index " < result < endl;
else
cout < "Element not found" < endl;
return 0;
}
public class BinarySearch {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid; // Target found at index mid
if (arr[mid] < target)
left = mid + 1; // Target is in the right half
else
right = mid - 1; // Target is in the left half
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11, 13, 15};
int target = 7;
int result = binarySearch(arr, target);
if (result != -1)
System.out.println("Element found at index " + result);
else
System.out.println("Element not found");
}
}
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid # Target found at index mid
elif arr[mid] < target:
left = mid + 1 # Target is in the right half
else:
right = mid - 1 # Target is in the left half
return -1 # Target not found
# Example usage
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)
if result != -1:
print("Element found at index", result)
else:
print("Element not found")
Analysis of Binary Search
Time Complexity
The algorithm's basic operation is comparison. If A[mid] == key, the basic operation comparison decides the time complexity of the binary search algorithm. Time complexity of the binary search algorithm is based on how many times the comparison operation is performed.
Best Case: If the search key is present in the first A[mid], the binary search algorithm performs only one comparison.
Best(n) = 1
Best(n) = O(1); order of growth is constant.
Worst Case: If the search key is present in the last A[mid] or not present at all, the binary search algorithm performs a maximum of log n comparisons.
a) The worst case situation occurs when the search key is present in the last location of the array.
b) The search key is not present in the array.
Worst(n) = log n,
Worst(n) = O(log n); order of growth is logarithmic. The average case complexity of binary search is O(log n).
Space Complexity
The binary search algorithm requires memory for the array A and the search key. No extra memory is required. The space complexity of binary search is O(1).
