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

    return -1  # Element not found

# 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:
    print(f"Element {target_element} not found.")

In this implementation, binary_search takes a sorted list (arr) and a target element (target). It initializes low and high indices to represent the search range. The while loop continues until the search range is valid (low is less than or equal to high). In each iteration, it calculates the middle index (mid) and compares the middle element with the target. Depending on the comparison, it updates the search range. If the target element is found, the function returns the index of the element. Otherwise, it returns -1 to indicate that the element is not in the list. The example usage demonstrates how to use the function with a sorted list and a target element.

Copy The Code & Try With Live Editor

#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 {
            System.out.println("Element not found in the array");
        }
    }
}

This implementation assumes that the input array is sorted. The binarySearch method takes a sorted array and a target element as parameters and returns the index of the target element in the array if found, otherwise, it returns -1. In the example provided, the target element is 5, and the program will output "Element found at index 4" because 5 is present at index 4 in the sortedArray.

Copy The Code & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor
Advertisements

Demonstration

Binary Search Data Structure and Algorithm