Binary Search: Error in Passing Array

Binary search program cause runtime error and failed hidden test cases

The only thing wrong with your second implementation is using size_t. Change it to int, and it ought to work fine.

size_t is an unsigned type. The value of end can be negative when the search is probing the beginning of the array. This invokes undefined behavior in C. In practice, that usually means the value "underflows" and becomes a huge positive number.

Binary search in array is not working properly

Assuming that you are passing n as the size of the array, you should give e = n-1 since arrays are 0-indexed based, that is where you are probably getting the wrong answer.
And you also should calculate mid after each iteration, so it should be inside the while loop.

Also, you should do mid = s +(e-s)/2 to avoid overflow.

Binary Search cannot find the first value in the array list

Your problem is with bounds when you move your indexes.
Just change last instructions as followinng :

last_index = mid_point + 1; ==> last_index = mid_point - 1;

first_index = mid_point - 1; ==> first_index = mid_point + 1;

My binary search function in Python is not working

Firstly before solving problem let's discuss binary search,

Binary Search: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half.

Here you need to change midpoint every time when while loop completes it's single loop and then you need to check if item is in lower half or upper half if it is present in lower half then you need to change end-point not start-point and if in upper half then change lower-point

And one important thing, in your while condition if element is not present then it will be in infinite loop so your while loop condition must be while(end_point > start_point) because we are changing points in each loop.

Code for reference:

def binary_search(array,item):
    start_point = 0
    end_point = len(array)
    array.sort()
    print(array)
    while end_point > start_point:
        mid_point = int((start_point + end_point) / 2)
        if array[mid_point] < item:
            start_point = mid_point+1
        elif array[mid_point] > item:
            end_point = mid_point-1
        elif array[mid_point] == item:
            print(mid_point)
            return
    print("ELement is not present")

binary_search([0,99,2,6,7,8],3)

Why is binary search function not working when values on pointers are compared instead of the pointers themselves?

Check out the way you calculate the mid value.

In the first iteration, mid=(p+(r/2)) will give you the middle term correctly. Let say r=5, and that in the first iteration we got *mid<num so now p=mid+1 or p=p+3.
The problem now is that r is still 5 so the array pointer just got shifted away from its values without marking the new end. This can easily lead to segmentation fault if you will try to use your result address later.

the solution is simple: don't calculate the mid position with a pointer and int. Use two pointers to mark the search bounders or two integers to mark their indexes.
You can also use your way, but be sure to update r size every iteration.

First option - using indexes (my choice if I had to make one):

int binarysearch(int*p,int r,int num){
    int mid;
    int a=0;
    while(a<=r) {
        mid=(a+r)/2;
        printf("1 ");
        if(p[mid]==num)
            return *mid;
        else if(p[mid]<num)
            a=mid+1;
        else if(a==r)
            break;
        else
            r=mid;
    }
    return -1;
}

Second option - your fixed version:

int binarysearch(int*p,int r,int num){
    int *mid;
    while(r>=0) {
        mid=p+(r/2);
        printf("1 ");
        if(*mid==num)
            return *mid;
        else if(*mid<num) {
            p=mid+1;
            r-=(r/2)+1;
        }
        else if (r==0)
            break;
        else
            r/=2;
    }
    return -1;
}

My basic binary search method does not work for one specific value in an int array in Java

The problem is that even though you're changing low and high, the loop depends on variable i which only changes through being incremented at the end of each iteration of the loop. However, the terminating condition for binary search should be when low >= high. The loop condition you have now, i < high has nothing to do with the relationship between low and high, which could cause the loop to end prematurely or keep going when the binary search has already ended.

What I'd suggest is doing is initializing low in the for loop, changing the terminating condition to low <= high, and making the update sequence mid = (low + high)/2 since you do that after each iteration of the for loop unless you find the number. At that point, however, the loop will terminate returning the index of the found number. Here's what it would look like,

public static int findNumber(int key, int... numbers) {
    int high = numbers.length - 1;
    int mid = (0 + high) / 2; //replaced low with 0 here
    int rank = 0;
    for (int low = 0; low <= high; mid = (low + high) / 2) {
        if (key < numbers[mid]) {
            high = mid - 1;
        } else if (key > numbers[mid]) {
            low = mid + 1;
        } else {
            rank = mid;
            return rank;
        }
    }
    return rank;
}

EDIT: So after some testing, I realized that another error was how you were updating low and high in your method. When updating these variables before, you were simply doing high = mid and low = mid but this is risky because by doing this, you're essentially still keeping numbers[mid] within the range that's going to be evaluated in the next iteration of the loop. This number, numbers[mid] should be omitted from the range, since the key is either going to be less than, greater than, or equal to numbers[mid]. If the key is less than or greater than numbers[mid], then there's no point in keeping it going forward to the next range of numbers to be looked at by binary search. So a solution would be to update low and high by low = mid + 1 and high = mid - 1.

---

Related Topics