We will discuss the Binary Search Algorithm, pseudo code, Code implementation of Binary Search Algorithm in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Binary Search Algorithm.

## Table of Contents

## 1. What is Binary Search?

**Binary Search** is the most popular search algorithm. It is efficient and most commonly used to solve problems.

**Binary Search** relies on a divide-and-conquer strategy to find an element within a sorted list.

** Binary Search** compares the element to be searched with the middle element of an array. If the element is equal to the middle element, the search stops here and the position of an element is returned. If it is less or greater than the middle element, then the values of the sub-array are adjusted accordingly. The algorithm returns a unique value: the element’s position in the list if the element is present.

Binary search works only on a sorted array. To use binary search, the array must be sorted first.

### 1.1 Pseudocode for Binary Search

BINARY_SEARCH (A, value, left, right)

1. if right < left

2. return ‘not found’

3. mid = floor((right-left)/2)+left

4. if A[mid] = value

5. return mid

6. if value < A[mid]

7. return BINARY_SEARCH(A, value, left, mid-1)

8. else

9. return BINARY_SEARCH(A, value, mid+1, right)

## 2. Implementation of Binary Search Algorithm

### 2.1 Binary Search Algorithm in C

#include <stdio.h> int binarySearch(int arr[], int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } int main() { int arr[] = {3, 15, 8, 1, 38, -2, 7}; int n = sizeof(arr) / sizeof(arr[0]); int target = 8; int result = binarySearch(arr, 0, n - 1, target); if (result != -1) printf("Element found at index %d\n", result); else printf("Element not found\n"); return 0; }

#### 2.1.1 Code Explanation of Binary Search

**binarySearch**function takes an array**arr[]**, the lower bound**low**, the upper bound**high**, and the element to be searched**x**.- It performs binary search iteratively using a
**while**loop. - It calculates the middle index
**mid**as**(low + high) / 2.** - If the middle element is equal to
**x**, it returns the index. - If the middle element is less than
**x**, it updates the lower bound to**mid + 1**. - If the middle element is greater than
**x**, it updates the upper bound to**mid-1**. - The loop continues until the element is found or until the
**low**is greater than the**high**. - In the
**main**function, an array**arr[]**is defined along with its size**n**and the element to be searched**x**. - The
**binarySearch**function is called with appropriate arguments, and the result is printed.

### 2.2 Binary Search Algorithm in C++

#include <iostream> #include <vector> using namespace std; int binarySearch(vector<int>& arr, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } int main() { vector<int> arr = {3, 15, 8, 1, 38, -2, 7}; int n = arr.size(); int target = 8; int result = binarySearch(arr, 0, n - 1, target); if (result != -1) cout << "Element found at index " << result << endl; else cout << "Element not found" << endl; return 0; }

### 2.3 Binary Search Algorithm in Java

public class BinarySearch { public static int binarySearch(int[] arr, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } public static void main(String[] args) { int[] arr = {3, 15, 8, 1, 38, -2, 7}; int target = 8; int result = binarySearch(arr, 0, arr.length - 1, target); if (result != -1) System.out.println("Element found at index " + result); else System.out.println("Element not found"); } }

### 2.4 Binary Search Algorithm in JavaScript

function binarySearch(arr, left, right, target) { while (left <= right) { let mid = Math.floor((left + right) / 2); if (arr[mid] === target) return mid; if (arr[mid] < target) left = mid + 1; else right = mid - 1; } return -1; } let arr = [3, 15, 8, 1, 38, -2, 7]; let target = 8; let result = binarySearch(arr, 0, arr.length - 1, target); if (result !== -1) console.log("Element found at index " + result); else console.log("Element not found");

### 2.5 Binary Search Algorithm in Python

def binary_search(arr, left, right, target): while left <= right: mid = left + (right - left) // 2 if arr[mid] == target: return mid if arr[mid] < target: left = mid + 1 else: right = mid - 1 return -1 arr = [3, 15, 8, 1, 38, -2, 7] target = 8 result = binary_search(arr, 0, len(arr) - 1, target) if result != -1: print("Element found at index", result) else: print("Element not found")

## 3. Time Complexity of Binary Search

Time Complexity | |

Worst Case | O(log n) |

Best Case | O(1) |

Average Case | O(log n) |

Space Complexity | |

Worst Case | O(n) |

## 4. Advantages of Binary Search

- Efficient for searching in sorted arrays.
- Time complexity is O(log n), which means it’s highly efficient for large datasets.

## 5. Disadvantages of Binary Search

- Requires the array to be sorted beforehand.
- If the array is not sorted, a sorting operation needs to be performed first, which could be an additional overhead.
- Binary search is not suitable for linked lists or data structures where direct access to elements is not efficient.

*FAQs*

*FAQs*

### How does a binary search algorithm work?

** Binary Search** compares the element to be searched with the middle element of an array. If the element is equal to the middle element, the search stops here and the position of an element is returned. If it is less or greater than the middle element, then the values of the sub-array are adjusted accordingly. The algorithm returns a unique value: the element’s position in the list if the element is present.

### When to use Binary Search?

Binary Search is highly efficient for large datasets and searching in sorted arrays.

### What is the complexity of a linear search algorithm?

The Time Complexity of the Linear Search algorithm is *O(log n)* and the Space Complexity is *O(n)*.