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

1
2
3


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

1
2
3


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

Example 3

1
2
3


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

Example 4

1
2
3


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

1
2
3


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

Initialize left = 0 and right = N - 1 boundaries
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
If element not found, return false

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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

Constraint Handling: The prohibition of multiplication, division, and bit-shifts forces creative approaches to mid calculation
Division Simulation: We can simulate division by 2 through repeated subtraction or addition
Trade-offs: The constraint adds a log N factor to the time complexity compared to standard binary search
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.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Example 4#

Example 5#

Solution#

Method 1 - Addition-Based Mid Calculation#

Intuition#

Approach#

Code#

Complexity#

Method 2 - Optimized Addition-Based Approach#

Intuition#

Approach#

Code#

Complexity#

Method 3 - Recursive Addition-Based Binary Search#

Intuition#

Approach#

Code#

Complexity#

Performance Comparison#

Key Insights#

Edge Cases Handled#

Problem

Examples

Example 1

Example 2

Example 3

Example 4

Example 5

Solution

Method 1 - Addition-Based Mid Calculation

Intuition

Approach

Code

Complexity

Method 2 - Optimized Addition-Based Approach

Intuition

Approach

Code

Complexity

Method 3 - Recursive Addition-Based Binary Search

Intuition

Approach

Code

Complexity

Performance Comparison

Key Insights

Edge Cases Handled