Binary Search – Searching algorithms

Binary Search: Efficient Searching Technique

Binary search is a classic algorithm in computer science, used to find an element in a sorted array with a time complexity of O(log n). It significantly reduces the search space by dividing it in half during each iteration. This makes it one of the most efficient searching methods for sorted datasets.

---

How Binary Search Works:

1. Prerequisite: The dataset must be sorted in ascending or descending order.
2. Steps:
   • Compare the target value with the middle element.
   • If it matches, the search is complete.
   • If the target is smaller, search the left half.
   • If the target is larger, search the right half.
3. Repeat until the target is found or the search space becomes empty.

---

Java Implementation

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoid overflow
            if (arr[mid] == target) {
                return mid; // Target found
            } else if (arr[mid] < target) {
                left = mid + 1; // Search right half
            } else {
                right = mid - 1; // Search left half
            }
        }
        return -1; // Target not found
    }

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

Java Test Case

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class BinarySearchTest {
    @Test
    public void testBinarySearch() {
        int[] array = {1, 3, 5, 7, 9, 11};
        assertEquals(2, BinarySearch.binarySearch(array, 5));
        assertEquals(-1, BinarySearch.binarySearch(array, 4));
    }
}

---

Python Implementation

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid  # Target found
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half
    return -1  # Target not found

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

Python Test Case

import unittest

class TestBinarySearch(unittest.TestCase):
    def test_binary_search(self):
        array = [1, 3, 5, 7, 9, 11]
        self.assertEqual(binary_search(array, 5), 2)
        self.assertEqual(binary_search(array, 4), -1)

if __name__ == "__main__":
    unittest.main()

---

Similar Algorithms and Summary

Algorithm	Use Case	Time Complexity
Linear Search	Unsorted or small datasets	O(n)
Jump Search	Sorted arrays, larger datasets	O(sqrt{n})
Exponential Search	Arrays with unknown size	O(log n)

---