# Binary Search in Data Structure

Mentor: Shailendra Chauhan
Duration : 00:02:00

## What is Binary Search?

Binary search is an effective approach for retrieving an item from a sorted list of elements. It works by periodically dividing the portion of the list that might hold the item in half until only one location remains.

## Binary Search Algorithm

• Define the search interval as a full array or list.
• Finding a midway divides the search space in half.
• Check the center element against the key.
• If the key matches the middle element, the search is completed; return index.
• If the key does not match the middle element, select the next search space.
• If the key is less than the middle element, proceed to the left side of the search.
• If the key is greater than the middle element, proceed to the right side of the search.
• Repeat step 2.
• Continue the process until the key is found or the complete search space has been exhausted.

## Conditions for using Binary Search in a Data Structure

To implement the Binary Search algorithm:

• The data structure should be sorted.
• Access to any element of the data structure requires constant time.

## Implement Binary Search Algorithm in Data Structures

There are two basic techniques to implement the Binary Search Algorithm in Data Structures:

1. Recursive Binary Search
2. Iterative Binary Search

## Complexity Analysis of Binary Search

### Space Complexity

The space complexity, or O(1), of Binary Search is constant since no appreciable additional memory is used.

## Applications of Binary Search

• Libraries: Used in Java,.NET, and C++ STL libraries.
• Debugging: Helps in identifying faults during the debugging process.
• Machine Learning: Provides the foundation for advanced machine learning methods such as neural network training.
• Computer graphics: A component of texture mapping and ray tracing techniques.
• Database Searches: Used to search databases.

• Faster than linear search, particularly for big arrays (O(logN)).
• More efficient than other temporal complexity algorithms such as interpolation or exponential search.
• Each cycle removes half of the list, considerably reducing the search space.
• Ideal for searching huge datasets on external memory.
• Works with rotating arrays.

• Requires a sorted array; not applicable to unsorted data.
• A data structure requires contiguous memory locations.
• Not suited for dynamically updated arrays; only works with static arrays.
• Elements must be equivalent to ensure good ordering.
• The recursive binary search requires stack space.

## Applications of Binary Search

• Machine Learning Applications
• Computer Graphics Utilization
• Database Search Implementation
Still have some questions? Let's discuss.