## Algorithm

Binary search is a popular algorithm used for searching an element in a sorted array or list. It follows the divide and conquer strategy to efficiently locate a target element. The basic idea is to repeatedly divide the search space in half until the target element is found or the search space is empty.

Here's a step-by-step explanation of how binary search works:

1. Initial Setup:

• Assume you have a sorted array or list.
• Set two pointers, `low` and `high`, initially pointing to the first and last elements of the array, respectively.
2. Middle Element:

• Calculate the middle index as `(low + high) / 2`.
• Access the middle element.
3. Comparison:

• Compare the middle element with the target element.
• If they are equal, the search is successful, and the index of the middle element is returned.
• If the middle element is less than the target, it means the target must be in the right half of the array. Adjust `low` to `mid + 1` and repeat the process.
• If the middle element is greater than the target, the target must be in the left half of the array. Adjust `high` to `mid - 1` and repeat the process.
4. Repeat:

• Repeat steps 2-3 until the target element is found or the search space is empty (when `low` is greater than `high`).

Binary search has a time complexity of O(log n), which makes it very efficient for large datasets compared to linear search algorithms.

## Code Examples

### #1 Binary Search implement in Python

```Code - Python Programming```

``````def binary_search(arr, target):
low, high = 0, len(arr) - 1

while low <= high:
mid = (low + high) // 2
mid_element = arr[mid]

if mid_element == target:
return mid  # Element found, return its index
elif mid_element < target:
low = mid + 1  # Discard the left half
else:
high = mid - 1  # Discard the right half

# Example usage:
sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target_element = 6

result = binary_search(sorted_list, target_element)

if result != -1:
print(f"Element {target_element} found at index {result}.")
else:
``````

Copy The Code &

### #2 Binary Search implement in Java

```Code - Java Programming```

``````public class BinarySearch {

// Returns the index of the target element in the array if found, otherwise returns -1
static int binarySearch(int[] array, int target) {
int left = 0, right = array.length - 1;

while (left  < = right) {
int mid = left + (right - left) / 2;

// Check if the target is present at the middle
if (array[mid] == target) {
return mid;
}

// If the target is greater, ignore the left half
if (array[mid]  <  target) {
left = mid + 1;
}
// If the target is smaller, ignore the right half
else {
right = mid - 1;
}
}

// Target element is not present in the array
return -1;
}

public static void main(String[] args) {
int[] sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int targetElement = 5;

int result = binarySearch(sortedArray, targetElement);

if (result != -1) {
System.out.println("Element found at index " + result);
} else {
}
}
}
``````

Copy The Code &

### #3 Binary Search implement in C

```Code - C Programming```

``````#include <stdio.h>

int binarySearch(int arr[], int left, int right, int target) {
while (left  < = right) {
int mid = left + (right - left) / 2;

// Check if the target is present at the middle
if (arr[mid] == target)
return mid;

// If the target is greater, ignore the left half
if (arr[mid]  <  target)
left = mid + 1;

// If the target is smaller, ignore the right half
else
right = mid - 1;
}

// If the target is not present in the array
return -1;
}

int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 6;

int result = binarySearch(arr, 0, n - 1, target);

if (result == -1)
printf("Element %d is not present in the array\n", target);
else
printf("Element %d is present at index %d\n", target, result);

return 0;
}
< /code>``````
``` This program defines a binarySearch function that takes an array (arr), the left and right indices of the subarray to be searched, and the target element to be found. The main function initializes a sorted array, calls binarySearch, and prints the result. Remember that the array must be sorted for binary search to work correctly. If the target is present in the array, the program will print its index; otherwise, it will indicate that the element is not present. Copy The Code & ```
``` #4 Binary Search implement in C++ Code - C++ Programming #include <iostream> #include <vector> using namespace std; // Binary search function int binarySearch(const vector<int>& arr, int target) { int low = 0; int high = arr.size() - 1; while (low < = high) { int mid = low + (high - low) / 2; // Check if the target is at the middle if (arr[mid] == target) { return mid; } // If the target is greater, ignore the left half if (arr[mid] < target) { low = mid + 1; } // If the target is smaller, ignore the right half else { high = mid - 1; } } // Target not found return -1; } int main() { // Example usage vector<int> sortedArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int target = 7; int result = binarySearch(sortedArray, target); if (result != -1) { cout << "Target found at index " << result << endl; } else { cout << "Target not found in the array" << endl; } return 0; } This implementation uses an iterative approach to perform binary search on a sorted vector. It maintains two pointers, low and high, and calculates the middle index (mid) in each iteration. If the target is found at the middle, it returns the index. Otherwise, it narrows down the search range by updating low and high based on whether the target is smaller or greater than the middle element. Make sure the array is sorted for binary search to work correctly. Copy The Code & Advertisements (adsbygoogle = window.adsbygoogle || []).push({}); Demonstration Binary Search Data Structure and Algorithm ```
``` ```
``` ```