How do you implement binary search to find an element in a sorted array?

Binary search is an efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half. Here’s a step-by-step explanation, an example, and code in various programming languages to help you understand and implement binary search.

Understanding Binary Search

Objective: Given a sorted array, find the position of a target value using binary search.

Steps to Implement Binary Search

1. Initialize Pointers: Set up two pointers: low (starting at the beginning of the array) and high (starting at the end of the array).
2. Calculate the Middle Index: Find the middle index of the current search range using (low + high) // 2.
3. Compare the Target Value:

• If the target value is equal to the middle element, return the middle index.
• If the target value is less than the middle element, narrow the search range to the left half (i.e., adjust high to mid - 1).
• If the target value is greater than the middle element, narrow the search range to the right half (i.e., adjust low to mid + 1).

1. Repeat the process until low exceeds high. If the target value is not found, return an indication that the value is not present (e.g., -1).

Example

Consider a sorted array: [1, 3, 5, 7, 9, 11]

Target Value: 7

1. Initialize low = 0 and high = 5 (last index).
2. Compute mid = (0 + 5) // 2 = 2. The middle element is 5.
3. Since 7 is greater than 5, adjust low to mid + 1 = 3.
4. Compute the new mid = (3 + 5) // 2 = 4. The middle element is 9.
5. Since 7 is less than 9, adjust high to mid - 1 = 3.
6. Compute the new mid = (3 + 3) // 2 = 3. The middle element is 7.
7. 7 is equal to the middle element, so the target is found at index 3.

Code Examples

1. Python

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

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Target not found

# Example usage
arr = [1, 3, 5, 7, 9, 11]
target = 7
index = binary_search(arr, target)
print(f"Target found at index: {index}")

2. JavaScript

function binarySearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;  // Target not found
}

// Example usage
const arr = [1, 3, 5, 7, 9, 11];
const target = 7;
const index = binarySearch(arr, target);
console.log(`Target found at index: ${index}`);

3. Java

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int index = binarySearch(arr, target);
        System.out.println("Target found at index: " + index);
    }
}

4. C++

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int low = 0;
    int high = arr.size() - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;  // Target not found
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11};
    int target = 7;
    int index = binarySearch(arr, target);
    std::cout << "Target found at index: " << index << std::endl;
    return 0;
}

5. C

using System;

class Program {
    public static int BinarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.Length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1;  // Target not found
    }

    static void Main() {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        int index = BinarySearch(arr, target);
        Console.WriteLine("Target found at index: " + index);
    }
}

To implement binary search:

1. Initialize low and high pointers.
2. Calculate the middle index and compare the target with the middle element.
3. Adjust the search range based on the comparison.
4. Repeat until the target is found or the range is exhausted.

The provided code in Python, JavaScript, Java, C++, and C# illustrates how to implement these steps and find the target value efficiently.