I want to insert an element in a sorted array (replacing an existing element)

```
[1, 2, 3, 4, 5]
```

for example to insert 0 and maintain the order it should replace 1

```
[0, 2, 3, 4, 5]
```

and to insert 6 and maintain the order it should replace 5

```
[0, 2, 3, 4, 6]
```

I want to use binary search and I created the following

```
int binary_search(int *a, int first, int last, int x) {
int mid;
while (first <= last) { /* was <, changed to <= */
mid = (first + last) / 2;
if (a[mid] == x)
return mid;
else if (a[mid] > x)
last = mid - 1;
else
first = mid + 1;
}
/* after the loop => first = last */
if (a[first] > x)
return first;
else
return first + 1;
}
```

Am I missing something and How do I prove that what I did leads to an always correct result?

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.

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"
```

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:

- 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.
- 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.
- If a[first] > x, then x can be inserted at position 'first'.
- 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 (a[first] == x)
return first;
else if(a[first] > x)
return first;
else
return first+1;
}
```

Similar Questions

Is there any way to maintain a sorted array of objects? For example, if I have an object with properties ID, Date, Name and a collection of these objects: $col = array(); public function addNewObject(

Answering to another question, I wrote the program below to compare different search methods in a sorted array. Basically I compared two implementations of Interpolation search and one of binary searc

When I added node into binary tree and trying to show information about it, info isn't showing. I think that i have some problems with references in recursive insert algorithm, but can't fix it. packa

I implemented a search function of elements of the list that it was a binary search returns the index of the element found. My curiosity is to have a method of the binary search you could print all oc

How to find the Nth largest node in a BST? Do I keep a count variable while doing In Order Traversal of a BST? Return the element when the count = N???

Recently I came across one interesting question on linked list. Sorted singly linked list is given and we have to search one element from this list. Time complexity should not be more than O(log n).

I want to understand more about binary searching, cause I don't really understand. Binary search requires a precondition that an array is sorted. I got that right? It seems like a method should check

I want to insert an element into the right place that order maintains in the sorted list. I allocated 2*n size for the array and filled the rest with 999 since they are not used currently. ordered_ins

I have this array (A) with n elements that are guaranteed to be sorted and I need to perform a binary search on them in a parallel system. I started off by making this binary search algorithm. It's it

The problem is to extend the binary search algorithm to find all occurrences of a target value in a sorted array in the most efficient way. Concretely speaking, the input of the algorithm are (1) a so

I am using MySQL database. I have one table having column with datatype binary(16). I need help with the insert statement for this table. Example: CREATE TABLE `assignedresource` ( `distid` binary(16)

Why is the worst case big-O for inserting N items into an empty binary search tree n^2? there are no balance checks.

I have an assignment on optimal binary search trees and some questions came up while doing it. I have found many of the links online helpful (just from a Google search) but I was wondering... Why must

What's the best way to create a balanced binary search tree from a sorted singly linked list?

I am trying to efficiently search weather a subclass implements a method that I have the name of in a string called _szMethodName. I can get an array of all the methods that the subclass implements by

Note: I've included the code for the insert in case that is where my error lies. I'm having trouble removing nodes in my binary search tree. I ran this through eclipse and the node's pointers seem t

I want to write a binary search for a string array in C. I have written this code and it compiles with no errors but when i try to search it gives no results. Any help would be appreciated. String is

I have a sorted list of elements : c f g o p q r t w I need to find element f using binary search,I did it. I have also found this element using linear search in 2 comparisons. Now I need to show th

I am looking for an element x in a sorted array. It compares xx or the array range equals to zero I am getting segmentation fault where I went wrong I couldn't find my code is below I am compiling in

can we use write a program in java for binary search using threads. one thread for dividing the array and one for sorting the array.

If I am attempting to minimize the height of a Binary Search Tree, are these the correct steps?: 1) produce a sorted array from the tree 2) reconstruct the tree by adding the sorted elements into the

The binary search returns wrong value even though the list is sorted. Here is the list: 1707 ABCD 1707 XXXX 1725 DEFG 1725 HIJK 1725 LMNOP I get this list from a file presorted as per the time (First

the question is simple: there is some way that the ordered array that returns me the qsort, is returned in reverse, ie I want to avoid the use of any auxiliary array to invest the resulting array us

What would be the quickest way to insert values into the correct position in a numpy sorted array. For example I would like to insert ever value of binto a: a = [1,1,2,4,7,7,11,13,13,13,15,20,25,26,27

I've recently send my CV to one company that was hiring PHP developers. They send me back a task to solve, to mesure if I'm experienced enough. The task goes like that: You have an array with 10k un

I want to do a binary search in python: def binarySearch(data, val): Where data is a sorted array and value is the value being searched for. If the value is found, I want to return the index (such th

I have an Array of Strings that are in order A-Z. I was wondering the best way to go about sorting them for a balanced binary search tree. My initial thought is to split the array up into the first ha

Write a bash script to do a binary search. Read student names and grades from a file into an array. Prompt the user for a student name. Find the name in the array and display the grade. The data in th

I need to write asm function in Delphi to search for max array element. So that wat I wrote. Got few prolbems here. First - mov ecx, len just dosen't work in right way here. Actually it replaces valu

insert operation is not happening for BST.can cause?-1 is null element in array. Linked list is not be for this code. void insert(int *Tree,int element) { int temp=0;/* first subscript*/ if(Tree[temp]

I'm doing a small Java work on Binary Search Tree but when I'm implementing the recursive insert of a node into the tree and display it, I don't get anything. I've been on it for a while now, I don't

JAVA Homework Can someone give me some pointers on what I am doing wrong here? Thanks. 16.Code a recursive solution for Exercise 11(f), Binary search of an array to locate the value a Key. public clas

We want to search for a given element in a circular sorted array in complexity not greater than O(log n). Example: Search for 13 in {5,9,13,1,3}. My idea was to convert the circular array into a regu

I was given some code that contains an Array of Person objects I am to write methods to do the binary search and to override the compareto method in the Person class to compare based on last name and

I understand how binary search trees are implemented, but I am not sure what are the advantages of using it over the hash tables that most programming languages have built into their standard librarie

Following my previous question, I would like now to put the Binary Tree values in a sorted array. So, first I used my numOfNodeswn function that counts total sum of nodes in my tree, I created an arr

I use standard binary search to quickly return a single object in a sorted list (with respect to a sortable property). Now I need to modify the search so that ALL matching list entries are returned.

I have a document with the following structure: { tags: ['bbb', 'aaa', 'ddd', 'ccc'] } and I want to create a view which returns the hash of the sorted tags array as key. My approach is to sort the t

I created a program that generates a random 10 number array, sorts the array with a bubble sort, and then uses a binary search to see if the value is in the array or not. All my code looks correct to

I have an issue where my items in my binary tree are being inserted incorrectly. I'm inserting strings in each node. I think I might be doing something wrong because it seems like I always end up with

So I have a vector, and I want the elements to be sorted at all times. How should I go about inserting an element into that vector and keeping the elements sorted when I pop them out. I looked into st

I want to add an element to a BinarySearchTree. I have a condition that checks if the element is already in the tree and if it is I want to throw an exception. My problem is that I do not know what ty

I'm using Schaum's Outline of Programming With Fortran 77 book, and there's an example about binary search using bracketing group of values method. First of all here's the code : INTEGER X(100) INTE

Motivation: I want to use bsearch (binary search) to quickly search through a sorted list of 121-bit non-negative integers (they all have exactly 121 bits, although they may have leading zeroes). Thes

Given an element and an array, the Ruby#index method returns the position of the element in the array. I implemented my own index method using binary search expecting mine would outperform the built-i

I was thinking of implementing a binary search trees. I have implemented some very basic operations such as search, insert, delete. Please share your experiences as to what all other operations i coul

e.g, if you have a sorted array of the struct: struct Item{ int val; string property; } How would you go about using these with assumeSorted so that you could then search on Item.val? All the example

I'm trying to insert some binary data into database using 'mysql' gem in ruby. But as the binary data contains many single and double quotes, the following code fails. Please help me to fix it. m = my

Here is a c++ function to create a BST tree from an array of integers? It's simple. Take first element ,make root. Take next array element and insert it into the tree. Why is the loop starting from i=

I have been looking this for hours but i can not find a code which i want. for example array is : 45 16 22 51 18 72 33 64 40 binary must be : 45 16 0 22 0 72 0 0 18 33 0 0 64 0 0 0 0 It puts accordin