CPP

recursive binary search

int binarySearch(int[] A, int low, int high, int x)
{
    if (low > high) {
        return -1;
    }
    int mid = (low + high) / 2;
    if (x == A[mid]) {
        return mid;
    }
    else if (x < A[mid]) {
        return binarySearch(A, low,  mid - 1, x);
    }
    else {
        return binarySearch(A, mid + 1,  high, x);
    }
}

binary search recursive

"""Binary Search
Recursive
	- 2 Separate functions
    	--> Perhaps more readable?
    - Or just one function that recursively calls itself
		--> Perhaps more logical?
"""

## With 2 separate functions
def bin_recur(lst, item):
    return go_bin_recur(lst, item, 0, len(lst) - 1)
    
def go_bin_recur(lst, item, low, high):
    if low <= high:
        mid = (low + high) // 2
        if item > lst[mid]: # To the left
            low = mid + 1 
        elif item < lst[mid]: # To the right
            high = mid - 1
        else: # Found
            return mid
        return go_bin_recur(lst, item, low, high)
    return [] # Not found


## With one function
def bin_recur(lst, item, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    if low <= high:
        mid = (low + high) // 2
        if item > lst[mid]: # To the left
            low = mid + 1 
        elif item < lst[mid]: # To the right
            high = mid - 1
        else: # Found
            return mid
        return bin_recur(lst, item, low, high)
    return [] # Not found

"""Whats your preference?"""

Binary Search in C-Recursive Method

int bSearch(int arr[], int left, int right, int target) {
    if (right >= left) {
        int mid = left + (right - left) / 2;
 
        if (arr[mid] == target)
            return mid;
 
        if (arr[mid] > target)
            return binarySearch(arr, left, mid - 1, target);
 
        return binarySearch(arr, mid + 1, right, target);
    }
    return -1;
}

C++, binary search recursive

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int ret = 0;
		
        if (nums.size() == 0)
            return -1;
  
        if (nums[nums.size()/2] < target) {
            vector<int> halfVec(nums.begin()+nums.size()/2+1,nums.end());
            auto retIdx = search(halfVec,target);
            if (retIdx == -1) return -1;
            ret += retIdx +  nums.size()/2+1;
        } else if (nums[nums.size()/2] > target) {
            vector<int> halfVec(nums.begin(),nums.begin()+nums.size()/2);
            ret = search(halfVec,target);
        } else {
            ret = nums.size()/2;
        }
         
        return ret;
        
    }
};