insert an element into a sorted array using binary search

What I usually do and I think it is the easiest way to prove the algorithm is correct is to think of it smallest unit. So let start by giving a scenario which algorithm might fail and test whether it will fail.

Assuming that the first = 0 and the last = 1. Then, the mid = (0 + 1 )/ 2 = 0. So there are 3 possible cases.

• When the a[mid] == x, then great, you found the answer.
• When the a[mid] > x, then you will move your, last = mid - 1 = -1. Great, you terminate because last is not greater than first and it is true because x is less than value of the first element of the sorted list, so it is impossible for x to be in the list.
• When the a[mid] < x. then you will move your first = mid + 1 = 1. Now, in this case, you terminate your loop. But, there is something wrong, because a[1] might hold the value of what you are looking for. You simply skip a possible option.

The following is a visualize of the case when your algorithm fail. Assuming the x = 5 and denote F = first and L = last.

      (1   5)   6   7   8   9   15
       ^   ^ 
       F   L

As you see, the bold part is the possible option. You have 2 possible options which is a[0] and a[1] when first = 0 and last = 1. Then when you calculate the mid = (0 + 1) / 2 = 0 and when you detect that a[mid] = a[0] = 1 < 5. Then you move your first = 1 and last = 1. You terminate the loop because last is no longer greater than first which in this case, you only check a[0], but you skip a[1].

So this is what I suggest to do

def binarysearch(a, x):
    low  = 0
    high = length(a)

    while low <= high:
        mid = (high + low) / 2
        if     (a[mid] == x): return mid
        elseif (a[mid] > x) : low  = mid + 1
        else                : high = mid - 1

    return -1

In your code, you do not have mechanism to tell whether the item you are searching for does not found. I return -1 when x is not found. So, you can simply create function replace in this way.

def replace(a, x, y):
    # replace x with y 
    i = binarysearch(a, x)
    if i >= 0:
        a[i] = y
    else:
        print "x does not exist"

Notice in your code. If you want to replace 5 with 6 in 0, 2, 3, 4, 5. first iteration: first = index 0, last = index 4, mid = index 2. 3 < 6 so now first is index 3, last is 4 still. Next iteration: first = index 3, last = index 4, mid = index 3. 4 < 6 so now first is index 4. 4 !< 4, so go to that if, else. a[4] is 5, 5 < 6, so return first + 1 which is index 5. That index is out of bounds now.

you need to make sure you don't go out of bounds. Also what if you have numbers 1 2 4 5 and you want to insert 3. What will you do, overwrite the 2 or the 4? both work. You will automatically replace the 4 via your code, but do you always want to replace the higher number, maybe you want to do the closest number instead? That's just something to think about.

I would like to suggest few modifications to your original code, and then you can be sure that your code will always give the correct result:

1. In the while loop, you have written while(first <= last): It should be changed to while(first < last) as after while loop, it will compare 'x' with a[first] (or a[last]). For this to happen, they must be same, i.e., loop must break at a condition "first=last" as well.
2. After while loop, we need to add a check if a[first] (or, a[last]) is equal to x. If it is, then simply return the value of this index.
3. If a[first] > x, then x can be inserted at position 'first'.
4. If a[first] < x, then x will be inserted at position 'first+1'.

Here is my version of your code:

int binary_search(vector<int> a, int first, int last, int x) {
    int mid;
    while (first < last) {
        mid = (first + last) / 2;
        if (a[mid] == x)
            return mid;
        else if (a[mid] > x)
            last =  mid - 1;
        else
            first = mid + 1;
    }
    if (start == a.size())
        return a.size();
    else if(a[first] > x)
        return first;
    else
        return first+1;
}

EDIT: Suppose we wish to insert 7 in {1,3,5,6}. For this, once we come out of the loop, we need to consider the final value of the 'start' variable. If it is equal to the size of array, then the new element goes at the end. I've updated the code accordingly.