Binary Search
Description
Binary Search is an efficient algorithm for finding a target value within a sorted array. It works by repeatedly dividing the search interval in half, eliminating half of the remaining elements with each iteration.
How It Works
- Find the middle element of the array
- If the target value is equal to the middle element, return its index
- If the target value is less than the middle element, repeat the search on the left half
- If the target value is greater than the middle element, repeat the search on the right half
- If the search interval is empty, the target is not in the array
Visualization
Enter a number and click Search to begin
Implementation
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Example usage
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6
result = binary_search(arr, target)
print(f"Found {target} at index: {result}")
#include <iostream>
#include <vector>
class BinarySearch {
private:
static void printArray(const std::vector<int>& arr) {
std::cout << "Array: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;
}
public:
static int search(const std::vector<int>& arr, int target) {
int left = 0;
int right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Prevents integer overflow
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Element not found
}
};
// Example usage
int main() {
std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 6;
std::cout << "Searching for: " << target << std::endl;
BinarySearch::printArray(arr);
int result = BinarySearch::search(arr, target);
if (result != -1) {
std::cout << "Element found at index: " << result << std::endl;
} else {
std::cout << "Element not found in array" << std::endl;
}
return 0;
}
public class BinarySearch
{
public static int Search(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2; // Prevents integer overflow
if (arr[mid] == target)
{
return mid;
}
if (arr[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1; // Element not found
}
private static void PrintArray(int[] arr)
{
Console.Write("Array: ");
Console.WriteLine(string.Join(" ", arr));
}
// Example usage
public static void Main(string[] args)
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int target = 6;
Console.WriteLine($"Searching for: {target}");
PrintArray(arr);
int result = Search(arr, target);
if (result != -1)
{
Console.WriteLine($"Element found at index: {result}");
}
else
{
Console.WriteLine("Element not found in array");
}
}
}
Advantages and Disadvantages
Advantages
- Very efficient for large datasets
- Logarithmic time complexity
- Simple to implement
Disadvantages
- Requires sorted input
- Only works with sequential access data structures
- Not suitable for small datasets (linear search might be faster)