Algorithm: Binary Search

Implementation with Recursion

Python

def binarysearch(number, list, start, end):
  if start > end:
    return None
m = (end + start) // 2
if number > list[m]:
    return binarysearch(number, list, m+1, end)
  elif number < list[m]:
    return binarysearch(number, list, start, m-1)
  else: 
    return m
list = [1,2,3,4,5,6,7,8,9,10]
print(binarysearch(3, list, 0, len(list) - 1))

C++

#include <iostream>
using namespace std;
int binarysearch(int target, int a[], int i, int j){
    int half = (i + j)/2;
    if (j < i){
        return -1;
    }
    else if(a[half] < target){
        return binarysearch(target, a, half+1, j);
    }   
    else if(a[half] > target){
        return binarysearch(target, a, i, half-1);
    }
    else{
        return half;
    }
}
int main()
{
    int a[9] = {1,2,3,4,5,6,7,8,9};
    cout<<binarysearch(3, a, 0, 8);
}

Implementation with Iteration

Python

def binarysearch(number, list, start, end):
  while end > start:
    mid = (start + end) // 2
    if number > list[mid]:
      start = mid + 1
    elif number < list[mid]:
      end = mid - 1
    else:
      return mid
  if start > end:
    return None
list = [1,2,3,4,5,6,7,8,9,10]
print(binarysearch(3, list, 0, len(list) - 1))

C++

#include <iostream>
using namespace std;
int binarysearch(int target, int a[], int size){
    int i = 0;
    int j = size-1;
    int half = (i + j)/2;
    if (j < i){
        return -1;
    }
    while(a[half] != target){
        half = (i + j)/2;
        if(a[half] < target){
            i = half+1;
        }
        if(a[half] > target){
            j = half-1;
        }
    }
    return half;
}
int main()
{
    int a[9] = {1,2,3,4,7,8,9};
    cout<<binarysearch(8, a, 7);
}