code to search numbers in an array not working for numbers not present in the array

Question

#include<iostream>
using namespace std;

//searching using linear search

int linear_search(int arr[], int n, int key){                 //time complexity - order(n)

    for(int i=0; i<n; i++)
    {
        if(arr[i]==key)
        return i;
    }
    return -1;
}


//searching using binary search

int binary_search(int arr[], int n, int key){                 //time complexity-nlog(n) sorted array                                       

    int start=0, end=n-1;
    int middle = (start+end)/2;
    while(start<=end)
    {
        if(arr[middle] == key)
        return middle;
        else if(arr[middle] < key)
        start = middle + 1;
        else if(arr[middle] > key)
        end = middle -1;
    }
    return -1;
}

int main()
{
    int arr[100];
    int n,key;
    cout<<"enter total elements \n";
    cin>>n;
    cout<<"enter array elements \n";
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    cout<<"enter number you wanna findd \n";
    cin>>key;

    int key1 = linear_search(arr, n, key);
    int key2 = binary_search(arr, n, key);

// I think this part might have a problem, but I cannot figure out what because this is such a simple code which according to me has no mistakes, but it still isn't working properly.

    if(key1 != -1)
    cout<<"The number "<<key<< " is found by linear search at position "<<(key1 +1)<<endl;
    else{
    cout<<"key not foound"<<endl;}

    if(key2 != -1)
    cout<<"The number "<<key<< " is found by binary search at position "<<(key2 +1)<<endl;
    else{
    cout<<"key not found";}
    return 0;

}

I was writing this code to search a number in an array using both linear and binary search. This code seems to work fine to find numbers that exist in the array, but it does not work for numbers that are not present in the array.

Answer 1

The issue in your binary search function is

int middle = (start+end)/2;
while(start<=end)
{
    if(arr[middle] == key)

You're not recalculating middle for each iteration, which is incorrect. It should ideally be

int middle;
while(start<=end)
{
    middle = (start+end)/2;
    if(arr[middle] == key)