 Binary Search Algorithm with Example Code

# Binary Search Algorithm with Example Code

Published
05th Sep, 2023
Views  13 Mins  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.

## What is Binary Search Algorithm?

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.

## How does Binary Search work?

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.

• Your list or array should be sorted in ascending order.
• "L" stands for the initial element, whereas "R" stands for the last element. By applying the formula (L+R)/2 to these values, we attempt to reduce the size of the center element. This method performs a floor function to get the appropriate center element.
• The next step is determining whether the middle element's value equals the target value. If the answer is affirmative, the search can be called off.
• All values from the middle element to the "R" value are deleted if the desired value is smaller than the middle element. Steps 2 and 3 are repeated after that.
• All the values from the center element to the "L" value are deleted if the desired value is higher than the middle element. Steps 2 and 3 are repeated after that.

## Binary Search Algorithm

### 1. Iterative Approach

```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```

### 2. Recursive Approach

```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```

### 3. Binary Search Algorithm Dry Run

1. Item to be searched=20

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

## Binary Search Algorithm in C

### 1. Iterative Binary Search in C

```#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);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
return 0;
}```

Output:

### 2. Recursive binary search in C

```#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);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
return 0;
}```

Output:

## The binary search algorithm in C++

### 1. Iterative binary search algorithm C++

```#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);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
}```

Output:

### 2. Recursive binary search C++

```#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);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
}```

Output:

## Binary Search Algorithm in Java

### 1. Iterative Binary Search in JAVA

```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
}
}```

Output:

### 2. Recursive binary search algorithm java

```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
}
}```

Output:

## Binary Search Algorithm in Python

### 1. Iterative binary search algorithm python

```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:
else:
print("Element not present")```

Output:

### 2. Recursive Binary Search in Python

```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:
else:
print("Element not present")```

Output:

## Binary Search Examples

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); // 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); // 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:

• Regardless of the amount of data, binary search is effective when used to sort data.
• The binary method randomly examines the data to identify the needed element rather than searching by going through the data in sequential order. The search cycles are shortened and become more precise as a result.
• Instead of utilizing equality comparisons, which are slower and frequently wrong, binary search compares the sorted data using an ordering concept.
• The algorithm splits the array's size in half after each cycle of search; hence, in the subsequent iteration, it will only operate on the array's remaining half.

## Advantages of Binary Search Algorithm • One of the quickest methods for perusing calculations is a binary search.
• It is used to determine a component's location within a direct cluster.
• It undermines strategy and eats away at the gap rule.
• When properly understood, the computation is actually quite simple.
• It serves as a significant and frequent library schedule for you.
• Large data sets are preferred for this method.
• For huge-size data, it is more effective.
• It uses a multidimensional array as its platform.

## Limitations of Binary Search Algorithm

• It is more confusing than a simple inquiry and is excessively excessive for small amounts of components.
• It only functions with organized and maintained records. That isn't possible if the rundown is constantly updated with new components.
• It only functions with component kinds for which there are fewer relationships. Some types can't be organized.
• If the list does not allow for unauthorized access, there is a significant loss of effectiveness. For instance, you want to move to the middle of the rundown quickly.
• Hash searches are one of the much faster search methods available. In any case, a hash query necessitates the coordination of the parts in a significantly more complicated information structure.

## Conclusion

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.

## Binary Search Algorithm FAQs

1What is the difference between a binary tree and a binary search tree?

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.

2What is the order of the binary search algorithm?

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.

3Why is the binary search algorithm more efficient?

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.  #### Abhresh Sugandhi

Author

Abhresh is specialized as a corporate trainer, He has a decade of experience in technical training blended with virtual webinars and instructor-led session created courses, tutorials, and articles for organizations. He is also the founder of Nikasio.com, which offers multiple services in technical training, project consulting, content development, etc.  