-1

When I Run my code And take input of array in ascending order from user the function which i have made runs and if the i search the middle number from array to find its location the code runs perfectly fine. But when i search the number from array which is not middle the code does not give me any output please fix this issue.

#include<iostream>
using namespace std;
 
void input_array(int arr[], int n);
int binary_search(int arr[], int n, int target);

int main()
{
     int limit;
    cout<<"Enter The Limit For An Array:- ";
    cin>>limit;

    int arr[limit];

    input_array(arr, limit);

    int target;

    cout<<"Enter The Number to find its position:- ";
    cin>>target;

    binary_search(arr, limit, target);

}

void input_array(int arr[], int n)
{
    cout<<"Enter The Number in Increasing Order "<<endl;

    for (int i = 0; i < n; i++)
    {
        cout<<i+1<<". Enter Number :- ";
        cin>>arr[i];
    }   
}

int binary_search(int arr[], int n, int target)
{
    int low = 0;
    int high = n-1;
    int mid;

    for (int i = 0; i < n; i++)
    {
        mid = (low+high) / 2;

        if (arr[mid] == target)
        {
            cout<<"The Position of The Given Target is :- "<<mid;
            return 0;
        }

        if (arr[mid] > target)
        {
            low = mid + 1;
        }
        
        else
        {
            high = mid - 1;
        }   
    }
    return -1;
}

i have created a program which is not working i dont know the reason why its not working kindly please solve my issue so i can proceed further.

StellarClown
  • 160
  • 8
temporary
  • 1
  • Please don't tag multiple languages, only the one you're actually program in. The problem is that the code isn't valid C++ either, since [C++ doesn't have variable-length arrays](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). Use `std::vector` instead. – Some programmer dude Nov 10 '22 at 07:11
  • 2
    Your logic is reversed: if the value in the middle of the array (`arr[mid]`) is greater than the `target`, then it means you should check the first half (`high = mid - 1`), but you are checking the second half (`low = mid + 1`) – Rafalon Nov 10 '22 at 07:12
  • Also, while you're doing a binary search, you can't really call it a "binary *function*". And do you remember the important requirement that the data need to be *sorted * for binary search to work? – Some programmer dude Nov 10 '22 at 07:13
  • 1
    Also please take some time to read [the help pages](http://stackoverflow.com/help), take the SO [tour], read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). And learn how to [edit] your questions to improve them. – Some programmer dude Nov 10 '22 at 07:14

2 Answers2

0

Try this instead:

while (low + 1 < high)
{
    int mid = (low + high) / 2;
    if (arr[mid] >= target)
        low = mid;
    else
        high = mid;
}

if (arr[high] >= target)
    return high;
if (arr[low] >= target)
    return low;

return -1;
  • This is code only without any explanation. How do you expect anyone (specifically beginners) to learn from this? – Rafalon Nov 10 '22 at 07:46
  • Please take some time to read or refresh [how to write good answers](https://stackoverflow.com/help/how-to-answer). Code-only answers without any kind of explanations tend to lead to [cargo cult programming](https://en.wikipedia.org/wiki/Cargo_cult_programming) which is bad. – Some programmer dude Nov 10 '22 at 07:47
0

You were simply cycling N times, where N is the size of the array while with binary search it cycles at most log (N) times. In addition to a trivial problem of inverted logic. Below I show you the part of the code how it should be modified.

int binary_search(int arr[], int n, int target) {
    int low = 0;
    int high = n-1;
    int mid;

    while(low <= high) {
        mid = (low+high) / 2;

        if (arr[mid] == target) {
            cout << "The Position of The Given Target is :- " << mid;
            return 0;
        }else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }   
    }
    return -1;
}

I hope I was clear. Don't worry about asking for more information

StellarClown
  • 160
  • 8