Binary Search Without Multiplication, Division and Bit-shift Operations

Problem

Given a sorted list of integers of length N, determine if an element x is in the list without performing any multiplication, division, or bit-shift operations.

Do this in O(log N) time.

Examples

Example 1

Input: arr = [1, 3, 5, 7, 9, 11, 13, 15], x = 7
Output: true
Explanation: Element 7 is present at index 3 in the sorted array.

Example 2

Input: arr = [2, 4, 6, 8, 10, 12], x = 5
Output: false
Explanation: Element 5 is not present in the array.

Example 3

Input: arr = [1, 2, 3, 4, 5], x = 1
Output: true
Explanation: Element 1 is present at index 0.

Example 4

Input: arr = [10, 20, 30, 40, 50, 60, 70, 80, 90], x = 90
Output: true
Explanation: Element 90 is present at the last index.

Example 5

Input: arr = [], x = 5
Output: false
Explanation: Empty array contains no elements.

Solution

Method 1 - Addition-Based Mid Calculation

Intuition

Since we cannot use multiplication, division, or bit-shift operations to calculate the middle index, we need an alternative approach. We can calculate the middle point using only addition and subtraction. The key insight is that mid = left + (right - left) / 2 can be rewritten using repeated addition to avoid division.

Approach

1. Initialize left = 0 and right = N - 1 boundaries
2. While left <= right:
   • Calculate mid using addition-based approach: find (left + right) / 2 without division
   • To calculate (left + right) / 2, we can use the fact that (a + b) / 2 = a + (b - a) / 2
   • For (b - a) / 2, we can repeatedly subtract 2 from (b - a) until we get the result
   • Compare arr[mid] with target x
   • If equal, return true
   • If arr[mid] < x, search right half: left = mid + 1
   • If arr[mid] > x, search left half: right = mid - 1
3. If element not found, return false

Code

C++

class Solution {
public:
    bool search(vector<int>& arr, int x) {
        int left = 0, right = arr.size() - 1;
        
        while (left <= right) {
            int mid = findMid(left, right);
            
            if (arr[mid] == x) {
                return true;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
    
private:
    int findMid(int left, int right) {
        int diff = right - left;
        int halfDiff = 0;
        
        // Calculate diff / 2 using repeated subtraction
        while (diff >= 2) {
            diff -= 2;
            halfDiff++;
        }
        
        return left + halfDiff;
    }
};

Go

func search(arr []int, x int) bool {
    left, right := 0, len(arr)-1
    
    for left <= right {
        mid := findMid(left, right)
        
        if arr[mid] == x {
            return true
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return false
}

func findMid(left, right int) int {
    diff := right - left
    halfDiff := 0
    
    // Calculate diff / 2 using repeated subtraction
    for diff >= 2 {
        diff -= 2
        halfDiff++
    }
    
    return left + halfDiff
}

Java

class Solution {
    public boolean search(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = findMid(left, right);
            
            if (arr[mid] == x) {
                return true;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
    
    private int findMid(int left, int right) {
        int diff = right - left;
        int halfDiff = 0;
        
        // Calculate diff / 2 using repeated subtraction
        while (diff >= 2) {
            diff -= 2;
            halfDiff++;
        }
        
        return left + halfDiff;
    }
}

Python

class Solution:
    def search(self, arr: List[int], x: int) -> bool:
        left, right = 0, len(arr) - 1
        
        while left <= right:
            mid = self._find_mid(left, right)
            
            if arr[mid] == x:
                return True
            elif arr[mid] < x:
                left = mid + 1
            else:
                right = mid - 1
        
        return False
    
    def _find_mid(self, left: int, right: int) -> int:
        diff = right - left
        half_diff = 0
        
        # Calculate diff // 2 using repeated subtraction
        while diff >= 2:
            diff -= 2
            half_diff += 1
        
        return left + half_diff

Complexity

• ⏰ Time complexity: O(log N * log N), where the first log N comes from binary search iterations and the second log N comes from the repeated subtraction to calculate mid
• 🧺 Space complexity: O(1), using only constant extra space

Method 2 - Optimized Addition-Based Approach

Intuition

We can optimize the mid calculation by using a more efficient approach. Instead of repeatedly subtracting 2, we can use the mathematical property that (a + b) / 2 = (a + b - (a + b) % 2) / 2. We can calculate (a + b) % 2 without division by checking if the sum is odd or even.

Approach

1. Use standard binary search structure with optimized mid calculation
2. Calculate mid as left + (right - left) / 2 where division is simulated efficiently
3. For division by 2, use the fact that we can build the result by repeated addition
4. Use a more efficient approach: start with left, then add half of the difference
5. To find half efficiently, we can use the fact that adding 1 repeatedly until we reach the target gives us the count

Code

C++

class Solution {
public:
    bool search(vector<int>& arr, int x) {
        int left = 0, right = arr.size() - 1;
        
        while (left <= right) {
            int mid = left + findHalf(right - left);
            
            if (arr[mid] == x) {
                return true;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
    
private:
    int findHalf(int n) {
        if (n == 0) return 0;
        
        int result = 0;
        int doubled = 0;
        
        // Find largest number such that 2 * result <= n
        while (doubled + doubled <= n) {
            doubled++;
            result++;
        }
        
        return result - 1;
    }
};

Java

class Solution {
    public boolean search(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + findHalf(right - left);
            
            if (arr[mid] == x) {
                return true;
            } else if (arr[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return false;
    }
    
    private int findHalf(int n) {
        if (n == 0) return 0;
        
        int result = 0;
        int doubled = 0;
        
        // Find largest number such that 2 * result <= n
        while (doubled + doubled <= n) {
            doubled++;
            result++;
        }
        
        return result - 1;
    }
}

Python

class Solution:
    def search_optimized(self, arr: List[int], x: int) -> bool:
        left, right = 0, len(arr) - 1
        
        while left <= right:
            mid = left + self._find_half(right - left)
            
            if arr[mid] == x:
                return True
            elif arr[mid] < x:
                left = mid + 1
            else:
                right = mid - 1
        
        return False
    
    def _find_half(self, n: int) -> int:
        if n == 0:
            return 0
        
        result = 0
        doubled = 0
        
        # Find largest number such that 2 * result <= n
        while doubled + doubled <= n:
            doubled += 1
            result += 1
        
        return result - 1

Complexity

• ⏰ Time complexity: O(log N * log N), similar to Method 1 but with more efficient constant factors
• 🧺 Space complexity: O(1), using only constant extra space

Method 3 - Recursive Addition-Based Binary Search

Intuition

We can implement binary search recursively while maintaining the constraint of not using multiplication, division, or bit operations. This approach uses the same mid calculation technique but with a recursive structure that might be more intuitive for some scenarios.

Approach

1. Implement recursive binary search with base cases
2. Use the same addition-based mid calculation from previous methods
3. Recursively search left or right half based on comparison
4. Return result when element is found or search space is exhausted

Code

C++

class Solution {
public:
    bool search(vector<int>& arr, int x) {
        return binarySearch(arr, x, 0, arr.size() - 1);
    }
    
private:
    bool binarySearch(vector<int>& arr, int x, int left, int right) {
        if (left > right) return false;
        
        int mid = left + divideByTwo(right - left);
        
        if (arr[mid] == x) {
            return true;
        } else if (arr[mid] < x) {
            return binarySearch(arr, x, mid + 1, right);
        } else {
            return binarySearch(arr, x, left, mid - 1);
        }
    }
    
    int divideByTwo(int n) {
        int count = 0;
        while (n > 1) {
            n -= 2;
            count++;
        }
        return count;
    }
};

Java

class Solution {
    public boolean search(int[] arr, int x) {
        return binarySearch(arr, x, 0, arr.length - 1);
    }
    
    private boolean binarySearch(int[] arr, int x, int left, int right) {
        if (left > right) return false;
        
        int mid = left + divideByTwo(right - left);
        
        if (arr[mid] == x) {
            return true;
        } else if (arr[mid] < x) {
            return binarySearch(arr, x, mid + 1, right);
        } else {
            return binarySearch(arr, x, left, mid - 1);
        }
    }
    
    private int divideByTwo(int n) {
        int count = 0;
        while (n > 1) {
            n -= 2;
            count++;
        }
        return count;
    }
}

Python

class Solution:
    def search_recursive(self, arr: List[int], x: int) -> bool:
        return self._binary_search(arr, x, 0, len(arr) - 1)
    
    def _binary_search(self, arr: List[int], x: int, left: int, right: int) -> bool:
        if left > right:
            return False
        
        mid = left + self._divide_by_two(right - left)
        
        if arr[mid] == x:
            return True
        elif arr[mid] < x:
            return self._binary_search(arr, x, mid + 1, right)
        else:
            return self._binary_search(arr, x, left, mid - 1)
    
    def _divide_by_two(self, n: int) -> int:
        count = 0
        while n > 1:
            n -= 2
            count += 1
        return count

Complexity

• ⏰ Time complexity: O(log N * log N), log N recursive calls with log N time for mid calculation each
• 🧺 Space complexity: O(log N), for the recursion stack depth

Performance Comparison

Method	Time Complexity	Space Complexity	Best Use Case
Addition-Based Iterative	O(log N × log N)	O(1)	Memory-constrained environments
Optimized Addition	O(log N × log N)	O(1)	Better constant factors
Recursive Addition	O(log N × log N)	O(log N)	Functional programming style

Key Insights

1. Constraint Handling: The prohibition of multiplication, division, and bit-shifts forces creative approaches to mid calculation
2. Division Simulation: We can simulate division by 2 through repeated subtraction or addition
3. Trade-offs: The constraint adds a log N factor to the time complexity compared to standard binary search
4. Alternative Approaches: Multiple ways to calculate mid point while respecting constraints

Edge Cases Handled

• Empty array
• Single element array
• Target at boundaries (first/last element)
• Target not present in array
• All elements equal to target

All methods maintain the O(log N) search behavior required by the problem while respecting the operational constraints.