➤ How to Code a Game
➤ Array Programs in Java
➤ Java Inline Thread Creation
➤ Java Custom Exception
➤ Hibernate vs JDBC
➤ Object Relational Mapping
➤ Check Oracle DB Size
➤ Check Oracle DB Version
➤ Generation of Computers
➤ XML Pros & Cons
➤ Git Analytics & Its Uses
➤ Top Skills for Cloud Professional
➤ How to Hire Best Candidates
➤ Scrum Master Roles & Work
➤ CyberSecurity in Python
➤ Protect from Cyber-Attack
➤ Solve App Development Challenges
➤ Top Chrome Extensions for Twitch Users
➤ Mistakes That Can Ruin Your Test Metric Program
The binary search algorithm in data structure | Binary search is an efficient algorithm for finding an item from a sorted list or array of items. Sometimes it is also known as half-interval search, logarithmic search, or binary chop.
Condition:- The array must be sorted in ascending order.
The binary search algorithm cannot be applied to unsorted arrays. This algorithm can be used when the list or array has terms occurring in order of increasing size (for instance: if the terms are numbers, they are listed from smallest to largest; if they are words, they are listed in lexicographic, or alphabetic, order). If the array or list is not sorted then before applying the binary search algorithm, first sort the array or list.
It can be written in two ways. These are,
a) Recursive approach
b) Iterative approach
Table of Contents
Binary Search using Recursion
In the recursive approach, the recursion technique is used. It is an example of the divide and conquers technique where bigger problems are divided into smaller problems. Like all divide and conquer algorithms binary search first divides the large array into smaller sub-arrays and then solves it recursively. we see it in detail.
Binary Search Algorithm in Recursive Approach
a) Take an array, initial index, size, and search key.
b) Find the middle term.
c) if middle term == search key then return index.
d) if middle term > search key then apply recursive call on the first half of the array.
e) else apply a recursive call on the second half of the array.
f) Repeat the process until the search key is not matched.
g) If not matched then return -1.
It can be written as,
int binarySearch(arr, low, high, key) {
if (high >= low) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid;
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
return binarySearch(arr, mid + 1, high, key);
}
return -1;
}The time complexity of this algorithm = O(log n)
How Recursive approach works?
In binary search using a recursive approach, we split the array from the middle into two subarrays of the same size or where one of these smaller lists has one fewer term than the other. Let us understand it through an example.
Array = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
Example
Assume the search term = 40. Then the steps in this algorithm,
- Find the middle term of the array. If the size of the array is odd then middle-index = (size – 1)/2 else middle-index = size/2. In our example, middle index = 10/2 = 5, and middle term is array[3] = 60
- Compare the middle term and search term. If the middle term > search term then it may exist in the first portion of the array else in the second portion of the array. Since 60 > 40 therefore search terms may exist only in the first portion of the array.
- Split the array into two parts from the middle index. The subarr1 = {10, 20, 30, 40, 50} and subarr2 = {60, 70, 80, 90, 100}.
- Since the array is sorted and 60 > 40, therefore search terms may exist only in the first sub-array. Forgot about the second sub-array, no use of it, only the first sub-array is required for the next step. Now, assume the original array = {10, 20, 30, 40, 50}, and search term = 40.
- Repeat the same process with the first sub-array. Find the middle term. The middle index = (5-1)/2 = 2, middle term is array[2] = 30
- Compare middle term with a search term, 30 < 40 therefore it may exist only in the second portion.
- Split array into two subarrays from the middle index. The new sub arrays are:- subarr1 = {10, 20} and subarr2 = {30, 40, 50}. Only subarr2 will be considered for the next steps, no use of subarr1. Now, assume array = {30, 40, 50} and search term = 40. Repeat the process.
- Find the middle term. The middle index = (3-1)/2 = 1 and the middle term is array[1] = 40.
- Compare the middle term and search term. Currently, both are equal and a match is found.
Binary Search Example using Recursion
Let us see an example of this algorithm using recursion in different programming languages. The logic remains the same in every programming language.
C Program for Binary Search using Recursion
#include <stdio.h>
// function for binary search
/* if match found then return index of search key
else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
if (high >= low) {
// find middle index
int mid = low + (high - low) / 2;
// find middle term and compare
if (arr[mid] == key) return mid; // key found
// If key is smaller than middle term, then
// it can only be present in left subarray
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
// Else the key can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, key);
}
// key not found
return -1;
}
// main function
int main()
{
int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 40; // search key
// find the array size
int size = sizeof(array)/sizeof(array[0]);
// search key
int index = binarySearch(array, 0, size, key);
if(index == -1)
printf("%d Not Found\n", key);
else
printf("%d Found at Index = %d\n", key, index);
return 0;
}Output:-
40 Found at Index = 3
Also See:- Program in C++
Java Program for Binary Search using Recursion
public class Search {
public static void main(String[] args) {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 40; // search key
// binary search
int index = binarySearch(arr, 0, arr.length, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
}
// Method for binary search
/* if match found then return index of search key
else return -1 */
public static int binarySearch(int[] arr, int low,
int high, int key) {
if (high >= low) {
// find middle index
int mid = low + (high - low) / 2;
// find middle term and compare
if (arr[mid] == key) return mid; // key found
// If key is smaller than middle term, then
// it can only be present in left subarray
if (arr[mid] > key)
return binarySearch(arr, low, mid - 1, key);
// Else the key can only be present
// in right subarray
return binarySearch(arr, mid + 1, high, key);
}
// key not found
return -1;
}
}Output:-
40 Found at Index = 3
Python Program for Binary Search using Recursion
# Python program for binary search using recursion
def BinarySearch(arr, low, high, key): #user-defined function
if high >= low: #check base case
mid = (high + low) // 2
if (arr[mid] == key):
return mid
elif (arr[mid] > key):
return BinarySearch(arr, low, mid - 1, key)
else:
return BinarySearch(arr, mid + 1, high, key)
else:
return -1
arr = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ] #array
key = 40 #search key
# calling function
result = BinarySearch(arr, 0, len(arr)-1, key)
# display result
if result != -1:
print(key, "Found at index", str(result))
else:
print(key, "not Found")Output:-
40 Found at index 3
Binary Search using Iterative approach
In this approach, instead of calling the method recursively, we use iteration to traverse the array and find the search key. Both approaches are quite the same, with two differences in implementation.
In a recursive method, there is no loop, and rather than passing the new values to the next iteration of the loop, it passes them to the next recursion. In the iterative method, the iterations can be controlled through the looping conditions, while in the recursive method, the maximum and minimum are used as the boundary condition.
Binary search algorithm in data structure using Iterative approach
To search for the integer x in the list/array a1, a2 , … ,an , where list/array is in ascending order (a1 < a2 < ··· < an) ,
- begin by comparing x with the middle term am of the list/array, where m = ⌊(n + 1)/2⌋.
- If x > am, the search for x is restricted to the second half of the list, which is am+1, am+2, …, an.
- If x is not greater than am, the search for x is restricted to the first half of the list, which is a1, a2, …, am.
- The search has now been restricted to a list with no more than ⌊n/2⌋ elements.
- Using the same procedure, compare x to the middle term of the restricted list.
- Then restrict the search to the first or second half of the list.
- Repeat this process until a list with one term is obtained.
- Then determine whether this term is x.
The algorithm can be written as,
int binary search (a: array, low, high, x: search-key) {
i := low; // i is left endpoint of search interval
j := high; // j is right endpoint of search interval
while (i < j) {
m := ⌊(i+j)/2⌋
if x > a[m] then i := m+1
else j := m
}
if x=a[i] then location := i
else location := -1
return location
}Code For Binary Search
Let us see examples using an iteration approach in different programming languages. The logic remains the same in every programming language.
C Program
#include <stdio.h>
// function for binary search
/* if match found then return index of search key
else return -1 */
int binarySearch(int arr[], int low, int high, int key) {
int i = low; // left index
int j = high; // right index
int mid = 0;
while(i < j) {
// find middle index
mid = (i+j) / 2;
// compare search key and middle term
if(key > arr[mid])
i = mid + 1;
else
j = mid;
}
// when i==j
if(key == arr[i])
return i; // key found
return -1; // key not found
}
// main function
int main()
{
int array[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 40; // search key
// find the size array
int size = sizeof(array)/sizeof(array[0]);
// search key
int index = binarySearch(array, 0, size, key);
if(index == -1)
printf("%d Not Found\n", key);
else
printf("%d Found at Index = %d\n", key, index);
return 0;
}Output:-
40 Found at Index = 3
Java Program
public class Search {
public static void main(String[] args) {
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
int key = 40; // search key
// binary search
int index = binarySearch(arr, 0, arr.length, key);
// int index = binarySearch(arr, key);
// display result
if (index == -1)
System.out.println(key + " not Found.");
else
System.out.println(key + " Found at Index = " + index);
}
public static int binarySearch(int[] arr, int low,
int high, int key) {
int i = low; // left index
int j = high; // right index
int mid = 0;
while(i < j) {
// find middle index
mid = (i+j)/2;
// compare search key and middle term
if(key > arr[mid])
i = mid + 1;
else
j = mid;
}
// when i==j
if(key == arr[i]) return i; // key found
return -1; // key not found
}
}Output:-
40 Found at Index = 3
Python Program
# Python program for binary search using recursion
def BinarySearch(arr, key): #user-defined function
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < key:
low = mid + 1
elif arr[mid] > key:
high = mid - 1
else:
return mid
return -1
arr = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ] #array
key = int(input('Enter search key: ')) #search key
# calling function
result = BinarySearch(arr, key)
# display result
if result != -1:
print(key, "Found at index", str(result))
else:
print(key, "not Found")Output:-
Enter search key: 10
10 Found at index 0
Enter search key: 60
60 Found at index 5
Binary Search Time Complexity
| Best-case time complexity | O(1) | When the search key present at the center (middle term) of the array/list. |
| Worst-case time complexity | O(log n) | When the search key is not available or at the extremity of the list. |
In the iterative method, the space complexity would be O(1). While in the recursive method, the space complexity would be O(log n).
For the small arrays linear search algorithm gives better performance compared to this algorithm, but for the large arrays if the array is in sorted order then this algorithm gives better performance compared to the linear search algorithm.
There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than this algorithm. However, it can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.
Q) Binary search algorithm cannot be applied to?
a) Sorted linked list
b) Sorted binary trees
c) Sorted linear array
d) Pointer array
View Answer
Answer:- a) Sorted linked listThe binary search algorithm is based on the logic of reducing input size by half in every step until the search succeeds or input gets exhausted. But in the case of the Linked list, we don’t have indexes to access items.
If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!
