Let's define a macro called max of size 20 and an array, arr, of size max, that is, 20 elements (you can increase the value of the max macro to any larger value as desired). Next, we will specify the length of the array. Let's say that the length you entered is 8, which is then assigned to the len variable. When prompted, enter the specified number of sorted elements. The sorted elements you enter will be assigned to the arr array, as follows:
Then, you will be prompted to enter the number you want to search for in the sorted array. Let's say you picked 45; this number will be assigned to the numb variable. We will invoke the binary_search function and all three items – the arr array, the numb variable containing the number to search for, and the length of the array in len – are passed to the function. The arr, numb, and len arguments will be assigned to the arr, pnumb, and plen parameters respectively.
In the binary_search function, we will initialize two variables: lindex to 0 and uindex to 7, that is, equal to the length of the array; these two indexes represent the lower and upper index locations of the array respectively. Because arrays are zero-based, the eighth element of the array will be found at index location 7. We'll set a while loop to execute for as long as the value of uindex is greater than or equal to the value of lindex.
To compare the search value with the middle value of the array, we will first compute the middle value; sum the values of lindex and uindex, and divide the result by 2. The output of (0+7)/2 is 3. Then, compare the value of the numb variable, that is, 45, with the value at location arr[3], derived from your computation, that is, with 34 (see Figure 9.2):
Because 45 is greater than 34, we will have to continue our search in the lower half of the array. However, since our list is sorted in ascending order, we can now concentrate our search in the lower half of the array.
Now, the value of lindex is set equal to mid+1, that is, 4. Again, execute the while loop because uindex, that is, 7, is still greater than lindex. We will now compute the middle value of the upper half of the array: (4+7)/2 = 5. The search value 45 will be compared with arr[5], that is, with 80. Because 45 is smaller than 80, we will continue our search in the lower half of the array, as follows:
Next, the value of uindex is set equal to mid-1, that is, equal to 4. And the value of lindex from our previous computation is also 4. We will again execute the while loop because 4=4. The middle value of the array will be computed as (4+4)/2, that is, the search value 45 will be compared with arr[4], which is 60.
Because 45 < 60, the value of uindex will be set to mid-1, that is, equal to 3. The while loop will exit because our uindex (3) is not greater than our lindex (4) any more. The binary_search function will return the nfound variable to the main function. The nfound variable contains some garbage value, which is then assigned to the found variable in the main function. In the main function, the values in the found and numb variables are compared. Because the garbage value is not equal to the value in the numb variable, 45, a message, Value 45 is not found in the list will be displayed on the screen.
Suppose you want to search for the value 15 now. The values of lindex and uindex will again be 0 and 7 initially. The while loop will execute and the middle value will be computed as (0+7)/2, which will be 3. The value of 15 will be compared with the corresponding location, arr[3], that is, with 34. The value of 15 is smaller than 34, so the upper half of the array will be considered to continue the binary search, as shown in the following figure:
The value of the uindex variable is set equal to mid-1, that is, 2. Because uindex is still greater than lindex, that is, 2 >=0, the while loop will execute again. Again, the middle value is computed as (0+2)/2, which is 1. This means that 15 is compared with the arr[1] element.
The value at the arr[1] location is 15 only; hence, the nfound variable is set to 15 in the binary_search function and the nfound variable is returned to the main function. In the main function, the value of the nfound variable will be assigned to the found variable. Because the value in the found and numb variables are the same, the message Value 15 is found in the list will be displayed onscreen.
The program is compiled using GCC, as shown in the following screenshot. Because no error appears on compilation, that means the binarysearch.c program has successfully been compiled into an EXE file, that is, to the binarysearch.exe file. On executing the executable file, if we try searching for a value that is not found in the list, we get the following output:
If we run the executable file again and enter a number that exists in the array, we may get the following output:
Voilà! We've successfully used binary search to locate an item in a sorted array. Now let's move on to the next recipe!