« Binary search recursively

Problem

Given an integer sorted array (sorted in increasing order) and an element x, find the x in given array using binary search. Return the index of x. Return -1 if x is not present in the given array.

Note : If given array size is even, take first mid.

Input format :

Line 1 : Array size

Line 2 : Array elements (separated by space)

Line 3 : x (element to be searched)

Sample Input :

6

2 3 4 5 6 8

5

Sample Output:

3

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int binarySearch(int input[], int start, int end, int element)
15{
16    if (start > end)
17    {
18        return -1;
19    }
20    int mid = (start + end) / 2;
21    if (input[mid] == element)
22    {
23        return mid;
24    }
25    else if (input[mid] > element)
26    {
27        return binarySearch(input, start, mid - 1, element);
28    }
29    else
30    {
31        return binarySearch(input, mid + 1, end, element);
32    }
33}
34
35int main()
36{
37    int input[100000], length, element, ans;
38    cin >> length;
39    for (int i = 0; i < length; i++)
40    {
41        cin >> input[i];
42    }
43    cin >> element;
44    ans = binarySearch(input, 0, length - 1, element);
45    cout << ans << endl;
46    return 0;
47}