Binary Search Exercise

 

The National Park Service needs to relocate a herd of 300 Elk Deer. In order to do this they need to locate a habitat that will support a herd of that size. Actually, the Park Service wants the herd to be able to grow to 350 animals in the new habitat.

So, they need to locate a site that has a carrying capacity large enough for the future growth of the herd. The carrying capacity is a measure of the theoretical maximum size of a herd that can be supported by a site. The actual size that can be supported by a habitat is less than the site's carrying capacity.

The Service has a systems dynamics model that is calibrated for Elk Deer herds of no more than 1000. Use the model to find the carrying capacity required to support a herd of 350 Elk Deer.

First run the model as is. How many actual Elk Deer can be supported, in the long run, by a habitat with a carrying capacity of 1000?

Now we want to change the value of the carrying capacity in the model to determine the value needed to support 350 Elk Deer. We could just start guessing until we found the answer. But, let's use a more systematic procedure, a binary search.

Step 1: Determine a value for the variable of interest (carrying capacity) that you are certain is higher than the value you are searching for. In this case we can use 1000 since it will support around 762 Elk Deer and we only need to support 350.

Step 2: Determine a value for the variable of interest (carrying capacity) that you are certain is lower than the value you are searching for. In this case we can use 350 since the carrying capacity needed will be more than the actual number of Elk Deer to be supported.

Step 3: Run the model with a value half way between the high and low values. In this case, run the model with a carrying capacity of 675.

Step 4: Determine if the value used (675) is too high or is too low. The model shows that a carrying capacity of 675 will support 515, so the value is too high.

Step 5: Run the model with a value half way between the new known high and low values. In this case, run the model with a carrying capacity half way between 675 and 350, i.e., 513.

Step 6: Repeat the action of Step 4. Since the size of the herd that can be supported is 391, 513 is larger than needed.

Step 7: Repeat the action of Step 5. The new high value is 513 and the low value is still 350, so run the model with a carrying capacity half-way in between, 432.

Step 8: Repeat the action of Step 4. Since the size of the herd that can be supported is 329, a carrying capacity greater than 432 is needed. So, we now know the value we are searching for is between 432 and 513.

Step 9: Repeat the action of Step 5. The high value is still 513 and the new low value is 432, so run the model with a carrying capacity of 473.

Step 10: Repeat the action of Step 4. Since the size of the herd that can be supported is 361, 473 is still larger than needed.

Step 11: Repeat the action of Step 5. The high is now 473 and the low value is still 432, so run the model with a carrying capacity of 453.

Step 10: Repeat the action of Step 4. Since the size of the herd that can be supported is 346, a carrying capacity greater than 453 is needed.

Step 11: Repeat the action of Step 5. The high is still 473 and the low value is now 453, so run the model with a carrying capacity of 463.

Step 12: The carrying capacity of 463 yields a practical herd size of 353 which is close to our target value (you can continue with the search if you would like to get even closer). So we have determined that a habitat with a carrying capacity of, say, 465 is needed to relocate the herd.

 

Summary of Binary Search Process

Target Herd Size: 350

Initial High and Low Values: 350 - 1000

Sequence of values tried -
carrying capacity and associated practical limit:

  • 675 - 515
  • 513 - 391
  • 432 - 329
  • 473 - 361
  • 453 - 346
  • 463 - 353


        |-----------------------------------------------|
        350                     675                    1000
                     513
              432
                  473
               453
                463

This process may seem laborious to you and not as much fun as just guessing. But, the importance of knowing systematic procedures such as this is that they can be carried out automatically for us by a computer program. This will provide accurate results very quickly.

Systematic processes, such as the binary search process, are called algorithms. A major emphasis of computer science is to develop efficient algorithms.

 

This is the end of the exercise.