#### Back-track Binary Search

The problem of Binary Search is that there is noise inside the data gotten by the sensors, and at some time, the noise may make the sensor get a wrong determination. For example, at certain time, sensor i get the temperature at current position is 25.5 Degree, and according to the data gotten before, the temperatures of positions next to this position are 26 and 24 respectively. Since the difference between 24 and 25.5 is greater than that between 25.5 and 26, sensor i decide to move to the position where the temperature is 24. However, the real fact may be that 25.5 contain certain noise and the temperature is actually 24.8 degree. So, the sensor should move to the position where the temperature is 26 degree. There is no chance for the sensor to recover from such a mistake since the position where the temperature is 26 degree will never be considered thereafter.

So, in the second algorithm, whenever a sensor find that the differences between its current read and the previous reads on both sides are almost the same, it will choose the bigger one as the direction of next movement, just as Binary Search does, and save the other one in a stack. When it finish the search in the first direction, it will go back and check the other direction at that point.

Following is the output of the Back-track Binary Search.

The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees