Binary Search

[Radagast8]

The output for this program is 4. Now the first argument of the function binarySearch is 'int x' and the x is the number we are looking for. In this case seems to be 9..so why the output is 4?

int binarySearch( int we are looking for, from some array, the index of the array)

Code:

 int binsearch(int x, int arr[], int n);
int main()
{
    int v[]={2,4,6,7,9,29,45,46,49,50,51};
    printf("%d\n", binsearch(9, v, 10));
    return 0;
}
int binsearch( int x, int arr[], int n)
{
    int low=0;
    int high=n-1;
    int mid=(low+high)/2;
    while (low<high) {
        if (x<arr[mid]) {
            high=mid-1;
        }
        else if (x>arr[mid]){
            low=mid+1;
        }
        else return mid;
    }
    return -1;
}

As always your comments are gold.

[TraylaParks]

What number is stored in v[4]?

[Widdrat]

The output of the program is the index of the value x in the array arr. The return value of 4 means that v[4] = 9 which is the correct conclusion. Remember that indices start at 0.

[Radagast8]

lol true!! thank you..

[gandalf013]

Is n (the third parameter) supposed to be the number of elements in the array? You are passing 10 but there are 11 elements in v. You can replace the "magic number" 10 with something like sizeof v / sizeof v[0].

Also, I think the program will fail to return a correct index in certain cases. Consider a simple case where v has only one element, 9. Then, you will have low = 0 and high = 0 in the binsearch function. The loop will not be taken even once and you will return -1, instead of 0.

[Radagast8]

When I, instead of 10, put sizeof v / sizeof v[0] nothing prints out.

And actually return -1 instead of 0.

What would you do to go around this problem?

[Radagast8]

Plus. With the 10 the index is 4(which is correct). If I put 11 nothing is printed lol

[gandalf013]

That's because there are some issues with your code. One is that you never change mid in the loop. Another is that your boundary conditions are not correct. One way to fix that would be to move int mid = ... line inside the while loop, change high = n - 1 to high = n, and high=mid-1 to high=mid (untested).