For enquiries call:
+1-469-442-0620
HomeBlogProgrammingBinary Search Algorithm with Example Code
In this post, the Binary Search Algorithm will be covered. Finding a certain element in the list is the process of searching. The method is deemed successful and returns the element's location if the element is present in the list. If not, the search is deemed fruitless. will be covered. Finding a certain element in the list is the process of searching. The method is deemed successful and returns the element's location if the element is present in the list. If not, the search is deemed fruitless.
The two most used search methods are linear search and binary search. We'll talk about the Binary Search Algorithm here.
The search method that performs well on sorted lists is a binary search. Therefore, we must ensure that the list is sorted before utilizing the binary search strategy to find an element.
The divide and conquer strategy is used in binary search, where the item is compared to the middle element of the list after the list is divided into two halves. The location of the middle element is returned if a match is discovered. Otherwise, depending on the outcome of the match, we search into either of the halves.
A quick search algorithm with run-time complexity of O is a binary search. Divide and conquer is the guiding philosophy behind this search algorithm. The data collection must be in sorted form for this algorithm to function correctly.
You can enroll in the Python Programming course to help you upskill your skills.
An element in a sorted array can be searched using the sorting process known as a binary search. To use binary search on an array, it must first be sorted because the approach only operates on sorted arrays. As the number of iterations in the binary search reduces, it is a searching approach that is superior to the liner search technique.
The binary search is justified by the assumption that there is a key. The value to be searched is stored in this key. The sum of the two values—the highest and lowest—is divided by two. The array's highest and lowest values, as well as its first and last elements. The key is then compared to the midpoint value.
If the mid is the same as the key, we receive the output immediately. The operation is repeated on the condensed array if the key is greater than mid; in this case, mid+1 becomes the lowest value. Otherwise, mid-1 becomes the greatest value, and the process is repeated on the reduced array if the key value is smaller than mid. An error message is shown if it cannot be located anywhere.
When all the names in the world are listed in alphabetical order, and you want to find the position of a particular name, binary search will find it in the 35 possible iterations.
The number of iterations can always be decreased when using binary search to conduct actions on a sorted set based on the value that is being searched.
Binary search compares the collection's middle item in an effort to find a specific item. If there is a match, the item's index is returned. The item is searched in the sub-array to the left of the middle item if the middle item is greater than the item. If not, the sub-array to the right of the middle item is searched for the item. Up until the subarray's size is reduced to zero, this process is repeated on the subarray as well.
An effective algorithm for narrowing down a list of things is a binary search. When you have reduced the number of potential sites to one, the method works by continually dividing the list section that could contain the item in half. Let's see how this algorithm is implemented step-by-step.
binarySearch(arr, size) loop until beg is not equal to the end midIndex = (beg + end)/2 if (item == arr[midIndex] ) return midIndex else if (item > arr[midIndex] ) beg = midIndex + 1 else end = midIndex – 1
binarySearch(arr, item, beg, end) if beg<=end midIndex = (beg + end) / 2 if item == arr[midIndex] return midIndex else if item < arr[midIndex] return binarySearch(arr, item, midIndex + 1, end) else return binarySearch(arr, item, beg, midIndex - 1) return -1
input:
0 | 1 | 2 | 3 | 4 |
10 | 11 | 16 | 20 | 23 |
beg=0, end=4, mid=2
0 | 1 | 2 | 3 | 4 |
10 | 11 | 16 | 20 | 23 |
beg=3, end=4, mid=3
0 | 1 | 2 | 3 | 4 |
10 | 11 | 16 | 20 | 23 |
An element found at index 3, So 3 will be returned.
If you are eager to learn to program, you must check out the Programming short course.
#include <stdio.h>
int binarySearch( int arr[], int item, int beg, int end) {
while (beg <= end) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] > item)
beg = midIndex + 1;
else
end = midIndex - 1;
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
return 0;
}Output:
answer: 1
#include <stdio.h>
int binarySearch(int arr[], int item, int beg, int end) {
if (end >= beg) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] < item)
return binarySearch(arr, item, beg, midIndex - 1);
return binarySearch(arr, item, midIndex + 1, end);
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
return 0;
}Output:
answer: 1
#include <iostream>
using namespace std;
int binarySearch(int arr[], int item, int beg, int end) {
while (beg <= end) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] > item)
beg = midIndex + 1;
else
end = midIndex - 1;
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
}Output:
answer: 1
#include <iostream>
using namespace std;
int binarySearch(int array[], int item, int beg, int end) {
if (end >= beg) {
int midIndex = beg + (end - beg) / 2;
if (array[midIndex] == item)
return midIndex;
if (array[midIndex] < item)
return binarySearch(array, item, beg, midIndex - 1);
return binarySearch(array, item, midIndex + 1, end);
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
}Output:
answer: 1
class BinarySearch {
int binarySearch(int arr[], int item, int beg, int end) {
while (beg <= end) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] > item)
beg = midIndex + 1;
else
end = midIndex - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = arr.length;
int item = 45;
int ans = ob.binarySearch(arr, item, 0, n - 1);
if (ans == -1)
System.out.println("Element not present");
else
System.out.println("answer: "+ans);
}
}Output:
answer: 1
class BinarySearch {
int binarySearch(int arr[], int item, int beg, int end) {
if (end >= beg) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] < item)
return binarySearch(arr, item, beg, midIndex - 1);
return binarySearch(arr, item, midIndex + 1, end);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = arr.length;
int item = 45;
int ans = ob.binarySearch(arr, item, 0, n - 1);
if (ans == -1)
System.out.println("Element not present");
else
System.out.println("answer: "+ans);
}
}Output:
answer: 1
def binarySearch(arr, item, beg, end):
while beg <= end:
mid = beg + (end - beg)//2
if arr[mid] == item:
return mid
elif arr[mid] > item:
beg = mid + 1
else:
end = mid - 1
return -1
arr = [13, 45, 65, 16, 117, 82, 19]
item = 45
ans = binarySearch(arr, item, 0, len(arr)-1)
if ans != -1:
print("answer: " + str(ans))
else:
print("Element not present")Output:
answer: 1
def binarySearch(arr, item, beg, end):
if end >= beg:
midIndex = beg + (end - beg)//2
if arr[midIndex] == item:
return midIndex
elif arr[midIndex] < item:
return binarySearch(arr, item, beg, midIndex-1)
else:
return binarySearch(arr, item, midIndex + 1, end)
else:
return -1
arr = [13, 45, 65, 16, 117, 82, 19]
item = 45
ans = binarySearch(arr, item, 0, len(arr)-1)
if ans != -1:
print("answer: " + str(ans))
else:
print("Element not present")Output:
answer: 1
let's see the programs of binary search examples in different programming languages.
A program to implement Binary search in C language:
Following is the binary search algorithm example:
#include <stdio.h>
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{ mid = (beg + end)/2;
/* if the item to be searched is present in middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than middle, then it can only be in left subarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than the middle, then it can only be in the right subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70}; // given array
int val = 40; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
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", val);
if (res == -1)
printf("\nElement is not present in the array");
else
printf("\nElement is present at %d position of array", res);
return 0;
} Output:
A program to implement Binary search in C++:
#include <iostream>
using namespace std;
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{
mid = (beg + end)/2;
/* if the item to be searched is present in the middle */
if(a[mid] == val)
{
return mid+1;
}
/* if the item to be searched is smaller than the middle, then it can only be in the left subarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than the middle, then it can only be in the right subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {10, 12, 24, 29, 39, 40, 51, 56, 70}; // given array
int val = 51; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
cout<<"The elements of the array are - ";
for (int i = 0; i < n; i++)
cout<<a[i]<<" ";
cout<<"\nElement to be searched is - "<<val;
if (res == -1)
cout<<"\nElement is not present in the array";
else
cout<<"\nElement is present at "<<res<<" position of array";
return 0;
} Output:
A program to implement Binary search in Java:
class BinarySearch {
static int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{
mid = (beg + end)/2;
if(a[mid] == val)
{
return mid+1; /* if the item to be searched is present in the middle
*/
}
/* if the item to be searched is smaller than the middle, then it can only
be in left subarray */
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
/* if the item to be searched is greater than the middle, then it can only be
in right subarray */
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
public static void main(String args[]) {
int a[] = {8, 10, 22, 27, 37, 44, 49, 55, 69}; // given array
int val = 37; // value to be searched
int n = a.length; // size of array
int res = binarySearch(a, 0, n-1, val); // Store result
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: " + val);
if (res == -1)
System.out.println("Element is not present in the array");
else
System.out.println("Element is present at " + res + " position of array");
}
} Output:
The binary search is a superior option to be utilized as a search algorithm for the reasons listed below:
A search is a tool that lets its user look for files, papers, and other kinds of data. A sophisticated search method known as a binary search detects and retrieves data from a sorted list of things.
Common names for binary search include logarithmic search and half-interval search.
Every time an element that is to be searched is located, the array is split in half.
By dividing by two the sum of the leftmost and rightmost index values, the binary algorithm locates the array's center. Depending on the element to be identified, the algorithm now removes either the lower or upper bound of items from the center of the array.
To locate the necessary element, the algorithm randomly explores the data. The search cycles are shortened and become more precise as a result.
Instead of employing equality comparisons, which are inefficient and erroneous, binary search compares the sorted data using an ordering concept.
Unsorted data is not a good candidate for a binary search.
We hope this article inculcates interest in you for programming. You can start your career in programming with the Java Developer course.
A Binary Tree is a basic structure with a simple rule that no parent must have more than 2 children. In contrast, the binary search tree algorithm is a variant of the binary tree following a particular order in which the nodes should be organized.
On sorted arrays, Binary search operates. An element in the middle of the array is first compared to the target value in a binary search. The element's position in the array is returned if the target value matches the element. The search continues in the lower half of the array if the target value is smaller than the element.
The fundamental benefit of binary search is that each entry in the list is not scanned. It searches for the first half of the list rather than through each entry. As a result, a binary search finds an element faster than a linear search.
| Name | Date | Fee | Know more |
|---|
