Project 2

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

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 left side
return binarySearch(arr, x, low, mid - 1)

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

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int binarySearch(vector<int> v, int To_Find)
{
int lo = 0, hi = v.size() - 1;
int mid;
// This below check covers all cases , so need to check
// for mid=lo-(hi-lo)/2
while (hi - lo > 1) {
int mid = (hi + lo) / 2;
if (v[mid] < To_Find) {
lo = mid + 1;
}
else {
hi = mid;
}
}
if (v[lo] == To_Find) {
cout << "Found"
<< " At Index " << lo << endl;
}
else if (v[hi] == To_Find) {
cout << "Found"
<< " At Index " << hi << endl;
}
else {
cout << "Not Found" << endl;
}
}

int main()
{
vector<int> v = { 1, 3, 4, 5, 6 };
int To_Find = 1;
binarySearch(v, To_Find);
To_Find = 6;
binarySearch(v, To_Find);
To_Find = 10;
binarySearch(v, To_Find);
return 0;
}