# Binary Search

Tobi here.

Binary search is a popular algorithm that is used to **quickly locate an item in a sorted list**. Unlike sequential search, which checks each element one by one, binary search cuts the search space in half at each step.

However, binary search works only for sorted lists i.e the elements have to be in ascending ordescending order

A simple analogy: Imagine searching for the word “Orange” in a dictionary. Instead of starting at the beginning (“A”) or at the end (“Z“) and scanning each page, you open near the middle and decide whether your target word is before or after that point.

### How Binary Search Works

1. **Start with the middle element**: In a sorted list, the first “guess” is the middle value of the sorted list.
    
2. **Compare the guess with the target**:
    
    * If the guess equals the target: **success**, return the index.
        
    * If the guess is less than the target: the target must be in the **right half**.
        
    * If the guess is greater than the target → the target must be in the **left half**.
        
3. **Iterate**: Narrow down the search space by moving the lower or upper bound to exclude the half that cannot contain the target.
    

### **Algorithm Steps**

1. **Initialize**
    
    * Set “low“ to the minimum possible value.
        
    * Set “high“ to the maximum possible value.
        
2. **Iterate until found**
    
    1. Compute the middle value (guess)
        
    2. Ask or check: Is the target equal to “mid”?
        
        * **Yes:** Stop- target found.
            
        * **No:** Continue.
            
    3. If the target is **less than** “mid”:
        
        * Eliminate the upper half: high= mid - 1
            
    4. If the target is **greater than** “mid“:
        
        * Eliminate the lower half: low = mid + 1
            
3. **Exit condition**
    
    * Stop when “low“ > ”high” (target not found).
        

In conclusion, binary search is an algorithm that demonstrates the power of divide and conquer. By starting in the middle, comparing, and eliminating halves of the search space, it finds targets quickly. However, it only works on **sorted data**.

**Code implementation**: [click here!](https://github.com/tobi-20/Data-Stuctures-and-Algorithms-/blob/main/binary_search.go)

Further reading: [Grokking Algorithms- Aditya Bhargava](https://www.amazon.com/Grokking-Algorithms-illustrated-programmers-curious/dp/1617292230)