This is still vague – what is the right portion and left portion? The simple answer is that it is the location to the left of Middle, i.e. Middle-1, or the location to the right of Middle, i.e. Middle+1.

You can see that the left portion is defined by location 1 to Middle-1 and the right portion is defined by location Middle+1 to N. This means our program can be slightly more precise:

Middle = CEIL(N/2)
If shelf(Middle) == target Then Book found
If shelf(Middle) < target Then 
	search Middle+1 to N 
Else
	search 1 to Middle-1

We now have an accurate expression of the first step in the search and we need the next step. We could, using a top-down approach start to fill in the details of the right and left search but this is where some abstract programming thinking comes into play. The first step searches a shelf of books from 1 to N. What we need is a routine that searches any portion of the shelf from say Start to End.

Then we could implement the first step using Start set to 1 and End set to N:

Start = 1
End = N
Middle=CEIL(N/2)
If shelf(Middle) == target Then Book found
If shelf(Middle) < target Then 
	Start = Middle+1
	Search Start to End 
Else
	End = Middle-1
	Search Start to End

This works for the first step and tells us how to do the second step by adjusting the start and end values. Using this approach Start and End always specifies the range of books to be searched and each step can simply update them. So what we have is a routine that works for any step. This suggests that all we need to do is put the search into a loop:

Start = 1
End = N
While book not found
	Middle = CEIL(N/2)
	If shelf(Middle) == target Then Book found Exit Loop
	If shelf(Middle) < target Then 
		Start = Middle+1
	Else
		End = Middle-1

This almost works. At the very start the first step searches the whole shelf from Start to End. The Middle value is calculated and then we work out how to adjust Start and End so that they specify the shelf locations to be searched on the next step and simply start over with these values. Each time through the loop the range being searched gets smaller until we find the book or run out of shelf to search. But Middle is repeatedly calculated using N and not the number of locations left to search.

The correct instruction is:

Start = 1
End = N
While book not found
    Middle =CEIL((End-Start+1)/2)
    If shelf(Middle) == target Then Book found Exit Loop
    If shelf(Middle) < target Then 
		Start = Middle+1
    Else
		End = Middle-1

Notice that the number of locations between Start and End is End-Start+1.

Unfortunately the loop only ends if we find the book. If we don’t find the book then Start and End cross over with Start becoming bigger than End and the search becomes silly with the number of locations being searched going negative.

This is a bug and it is a typical bug in that the program works as long as the book you are looking for is on the shelf, but it goes wrong if the book isn’t on the shelf. Such bugs are not easy to spot, let alone fix, because they usually only reveal themselves in specific situations. The solution is to test for running out of shelf space. This happens if Start>End. Notice it isn’t Start==End because this means that the shelf to be searched is just one book.

Start=1
End=N
While Start<=End
    Middle=CEIL((End-Start+1)/2)
    If shelf(Middle)==target Then Book found Exit Loop
    If shelf(Middle)<target Then 
		Start = Middle+1
    Else
		End = Middle-1

This is a routine that does the job without error, no matter how many books are being searched and irrespective of whether the book is present or not. The loop always ends and it either finds the book or doesn’t.

I hope that after this detailed explanation you understand how the routine works. It is precise enough to give to a machine to do the job – no humans needed. The level of detail is typical of this sort of program and the thinking needed to create it is typical of programming thought. For programs that involve repeating a step you need to find a way to express that step in a completely general way so that it can be included in a loop that updates the conditions.

It would also be sensible to make the routine into a function:

Function BinarySearch(Start, End, Target)
    While Start<=End
	Middle=CEIL((End-Start+1)/2)
	If shelf(Middle)==target Then Return Middle
	If shelf(Middle)<target Then 
		Start = Middle+1
	Else
		End = Middle-1
	Return Not Found

To search the shelf using it you would write something like:

result = BinarySearch(1,N, book)