C++ binary search

int binarySearch(int low,int high,int key)
{
   while(low<=high)
   {
     int mid=(low+high)/2;
     if(a[mid]<key)
     {
         low=mid+1;
     }
     else if(a[mid]>key)
     {
         high=mid-1;
     }
     else
     {
         return mid;
     }
   }
   return -1;                //key not found
 }

"""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?"""

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0
 
    while low <= high:
 
        mid = (high + low) // 2
 
        // If x is greater, ignore left half
        if arr[mid] < x:
            low = mid + 1
 
        // If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1
 
        // means x is present at mid
        else:
            return mid
 
    // If we reach here, then the element was not present
    return -1
 
 
// Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10
 
// Function call
result = binary_search(arr, x)
 
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

If you are setting mid = (left + right)/2, you have to be very careful.
Unless you are using a language that does not overflow such as Python,
left + right could overflow. 
One way to fix this is to use left+ (right−left)/2 instead.

If you fall into this subtle overflow bug, you are not alone.Even Jon Bentley's
own implementation of binary search had this overflow bug and remained 
undetected for over twenty years.

"""Binary Search
Iterative
"""

def bin_iter(lst, item, low=0, high=None):
    if high is None:
        high = len(lst) - 1
    while 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 []  # Not found

/*
Java Implementation of Binary Search Algorithm.
- Assuming the Array is Sorted (Ascending Order)
- returns the Index, if Element found.
- -1, if not found.
*/
public class BinarySearch {

    int binarysearch(int[] array, int element) {
        int a_pointer = 0;
        int b_pointer = array.length -1;
      	if (array[a_pointer] == element) return a_pointer;
        if (array[b_pointer] == element) return b_pointer;

        while(a_pointer <= b_pointer){
            int midpoint = a_pointer + (b_pointer - a_pointer) / 2;
          	if (array[midpoint] == element) return midpoint;
          
          	// ignoring the left half, if this is True.
            if (array[midpoint] < element) a_pointer = midpoint + 1;
          
          	// ignoring the right half, if this is True.
            else if (array[midpoint] > element) b_pointer = midpoint - 1;
        }
        return -1;	// Element not Found
    }
    public static void main(String[] args) {
        int[] list = {1, 2, 3, 4, 7, 9, 11, 12, 15, 19, 23, 36, 54, 87};
        System.out.println(binarysearch(list, 19));
    }
}

// Java implementation of iterative Binary Search
class BinarySearch {
    // Returns index of x if it is present in arr[],
    // else return -1
    int binarySearch(int arr[], int x)
    {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
 
            // Check if x is present at mid
            if (arr[m] == x)
                return m;
 
            // If x greater, ignore left half
            if (arr[m] < x)
                l = m + 1;
 
            // If x is smaller, ignore right half
            else
                r = m - 1;
        }
 
        // if we reach here, then element was
        // not present
        return -1;
    }
 
    // Driver method to test above
    public static void main(String args[])
    {
        BinarySearch ob = new BinarySearch();
        int arr[] = { 2, 3, 4, 10, 40 };
        int n = arr.length;
        int x = 10;
        int result = ob.binarySearch(arr, x);
        if (result == -1)
            System.out.println("Element not present");
        else
            System.out.println("Element found at "
                               + "index " + result);
    }
}

class Solution {
  public:
  int search(vector<int>& nums, int target) {
    int pivot, left = 0, right = nums.size() - 1;
    while (left <= right) {
      pivot = left + (right - left) / 2;
      if (nums[pivot] == target) return pivot;
      if (target < nums[pivot]) right = pivot - 1;
      else left = pivot + 1;
    }
    return -1;
  }
};

// Java Binary Search Algorithm
// ----------------------------

/* 
   Time Complexity
     Best Time Complexity:O(1)
	 Average Time Complexity:O(log n)
	 Worst Time Complexity:O(log n)
     
   Space Complexity
     No auxiliary space is required in Linear Search implementation.
	 Hence space complexity is:O(1)
*/

public class BinarySearch {

    // Searching using Recursive approach
    public static int Search(int arr[], int value, int start, int end) {
        int center = (start + end) / 2;

        if (start <= end) {
            if (value == center) {
                return center;
            }

            if (value < center) {
                return Search(arr, value, start, center - 1);
            }

            if (value > center) {
                return Search(arr, value, center + 1, end);
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int arr[] = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        int Index = Search(arr, 9, 0, arr.length);
        if (Index == -1) {
            System.out.println("Value Not Found");
        } else {
            System.out.println("Value found at Index: " + Index);
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

int binarySearch(int arr[], int l, int h, int key){
    if(l<=h){
        int mid = l + (h-l)/2;

        if(arr[mid] == key){
            return mid;
        }

        else if(arr[mid] > key){
            return binarySearch(arr, l, mid-1, key);
        }

        else if(arr[mid] < key){
            return binarySearch(arr,mid+1, h, key);
        }
    }       

    return -1;
}

int main(){
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int n = sizeof(arr)/sizeof(arr[0]);
    int key = 7;

    int result = binarySearch(arr,0,n-1,key);

    (result==-1)
        ? cout << "Element is not found in the array" << endl
        : cout << "Element is found at index " << result;

    return 0;

}

const numbers = [1, 2, 3,4,5,6,7,8,9,10];

function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);
        console.log(middle)
        if (sortedArray[middle] === key) {
            // found the key
            return middle;
        } else if (sortedArray[middle] < key) {
            // continue searching to the right
            start = middle + 1;
        } else {
            // search searching to the left
            
            end = middle - 1;
        }
    }
	// key wasn't found
    return -1;
}

console.log(binarySearch(numbers,4))

# A recursive binary search function. It returns location of x in
# given array arr[l..r] is present, otherwise -1
def binarySearch(arr, l, r, x):
   if (r >= l):
        mid = l + (r - l)/2;
         
   # If the element is present at the middle itself
   if (arr[mid] == x):
        return mid;
       
   # If element is smaller than mid, then it can only be present
   # in left subarray
    if (arr[mid] > x):
    return binarySearch(arr, l, mid-1, x);
   
    # Else the element can only be present in right subarray
    return binarySearch(arr, mid+1, r, x);
    
 # We reach here when element is not present in array
   return -1;
  
# This code is contributed by umadevi9616

// C++ program to implement iterative Binary Search
#include <bits/stdc++.h>
using namespace std;
 
// A iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    while (l <= r) {
        int m = l + (r - l) / 2;
 
        // Check if x is present at mid
        if (arr[m] == x)
            return m;
 
        // If x greater, ignore left half
        if (arr[m] < x)
            l = m + 1;
 
        // If x is smaller, ignore right half
        else
            r = m - 1;
    }
 
    // if we reach here, then element was
    // not present
    return -1;
}
 
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}

function binarySearchRicorsivo(array A, int p, int r, int v)
    if p > r
      return -1
     if v < A[p] or v > A[r]
       return -1
     q= (p+r)/2
     if A[q] == v
       return q
     else if A[q] > v
       return binarySearchRicorsivo(A,p,q-1,v)
     else
     

binarySearch(arr, x, low, high)
           if low > high
               return False 
   
           else
               mid = (low + high) / 2 
                   if x == arr[mid]
                   return mid
       
               else if x > arr[mid]        // x is on the right side
                   return binarySearch(arr, x, mid + 1, high)
               
               else                        // x is on the right side
                   return binarySearch(arr, x, low, mid - 1)

Input: arr[] = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}, x = 110
Output: 6
Explanation: Element x is present at index 6. 

Input: arr[] = {10, 20, 30, 40, 60, 110, 120, 130, 170}, x = 175
Output: -1
Explanation: Element x is not present in arr[].

// Implements linear search for names
 
#include <cs50.h>
#include <stdio.h>
#include <string.h>
 
int main(void)
{
    // An array of names
    string names[] = {"Bill", "Charlie", "Fred", "George", "Ginny", "Percy", "Ron"};
 
    // Search for Ron
    for (int i = 0; i < 7; i++)
    {
        if (strcmp(names[i], "Ron") == 0)
        {
            printf("Found\n");
            return 0;
        }
    }
    printf("Not found\n");
    return 1;
}

binarySearch(arr, x, low, high)
        repeat till low = high
               mid = (low + high)/2
                   if (x == arr[mid])
                   return mid
   
                   else if (x > arr[mid]) // x is on the right side
                       low = mid + 1
   
                   else                  // x is on the left side
                       high = mid - 1

class BinarySearchExample{  
 public static void binarySearch(int arr[], int first, int last, int key){  
   int mid = (first + last)/2;  
   while( first <= last ){  
      if ( arr[mid] < key ){  
        first = mid + 1;     
      }else if ( arr[mid] == key ){  
        System.out.println("Element is found at index: " + mid);  
        break;  
      }else{  
         last = mid - 1;  
      }  
      mid = (first + last)/2;  
   }  
   if ( first > last ){  
      System.out.println("Element is not found!");  
   }  
 }  
 public static void main(String args[]){  
        int arr[] = {10,20,30,40,50};  
        int key = 50;  
        int last=arr.length-1;  
        binarySearch(arr,0,last,key);     
 }  
} 

// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
 
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
 
        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;
 
        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
 
        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
 
    // We reach here when element is not
    // present in array
    return -1;
}
 
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}

// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
 
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
 
        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;
 
        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
 
        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
 
    // We reach here when element is not
    // present in array
    return -1;
}
 
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1)
        ? cout << "Element is not present in array"
        : cout << "Element is present at index " << result;
    return 0;
}