# 2004 AP CS AB MC #31 trace

As noted in the 2004 AB MC explanations, this problem is more appropriately solved by recognizing the algorithm as binary search. The trace below is presented as a demonstration of tracing. It is not a suggestion that this problem should be traced.

This trace uses the technique demonstrated in tracing recursive methods and some of the material from the more complex stack based trace with nested recursive calls. Familiarity with the material from those resources is assumed, including the notation.

Labeling the explicit parameters, as shown below, is an optional step that is helpful when a method accepts several parameters or uses the parameters in a complex way.

## Step 1: Setup & initial call stack

There are 2 recursive call within the method. Label the first `call 1` and the second `call 2`.

### Initial call stack

``````m(arr, low: 0, high: 7, num: 14)
``````

## Step 2: `mystery(0, 7, 14)`

• Computes `(0 + 7) / 2`, which is `3`
• Creates `mid` and sets its value to `3`
• Checks if `0 > 7`, which is `false`
• Checks if `arr[3]`, which is `26`, is `< 14`, which is `false`
• Checks if `arr[3]`, which is `26`, is `> 14`, which is `true`
• Stops at `call 2`
• Calls `mystery(arr, 0, 3 - 1, 14)`, which is `mystery(arr, 0, 2, 14)`

### Resulting call stack

``````m(arr, low: 0, high: 2, num: 14)
m(arr, low: 0, high: 7, num: 14)2    mid: 3
``````

## Step 3: `mystery(arr, 0, 2, 14)`

• Computes `(0 + 2) / 2`, which is `1`
• Creates `mid` and sets its value to `1`
• Checks if `0 > 2`, which is `false`
• Checks if `arr[1]`, which is `13`, is `< 14`, which is `true`
• Stops at `call 1`
• Calls `mystery(arr, 1 + 1, 2, 14)`, which is `mystery(arr, 2, 2, 14)`

### Resulting call stack

``````m(arr, low: 2, high: 2, num: 14)
m(arr, low: 0, high: 2, num: 14)1    mid: 1
m(arr, low: 0, high: 7, num: 14)2    mid: 3
``````

## Step 4: `mystery(arr, 2, 2, 14)`

• Computes `(2 + 2) / 2`, which is `2`
• Creates `mid` and sets its value to `2`
• Checks if `2 > 2`, which is `false`
• Checks if `arr[2]`, which is `25`, is `< 14`, which is `false`
• Checks if `arr[2]`, which is `25`, is `> 14`, which is `true`
• Stops at `call 2`
• Calls `mystery(arr, 2, 2 - 1, 14)`, which is `mystery(arr, 2, 1, 14)`

### Resulting call stack

``````m(arr, low: 2, high: 1, num: 14)
m(arr, low: 2, high: 2, num: 14)2    mid: 2
m(arr, low: 0, high: 2, num: 14)1    mid: 1
m(arr, low: 0, high: 7, num: 14)2    mid: 3
``````

## Step 5: `mystery(arr, 2, 1, 14)`

• Computes `(2 + 1) / 2`, which is `1`
• Creates `mid` and sets its value to `1`
• Checks if `2 > 1`, which is `true`
• Stops and returns `2`

### Resulting call stack

``````m(arr, low: 2, high: 1, num: 14)     mid: 1  returns 2
m(arr, low: 2, high: 2, num: 14)2    mid: 2
m(arr, low: 0, high: 2, num: 14)1    mid: 1
m(arr, low: 0, high: 7, num: 14)2    mid: 3
``````

The question asks how many calls are made. It is clear at this point that no further calls will be made. The trace is continued below as an example of recursive method tracing.

## Step 6: Back in `mystery(arr, 2, 2, 14)`

• Back in `mystery(arr, 2, 2, 14)`
• Finished `call 2`, got back `2`
• Stops and returns `2`

### Resulting call stack

``````m(arr, low: 2, high: 1, num: 14)     mid: 1  returns 2
m(arr, low: 2, high: 2, num: 14)     mid: 2  returns 2
m(arr, low: 0, high: 2, num: 14)1    mid: 1
m(arr, low: 0, high: 7, num: 14)2    mid: 3
``````

## Step 7: Back in `mystery(0, 2, 14)`

• Back in `mystery(0, 2, 14)`
• Finished `call 1`, got back `2`
• Stops and returns `2`

### Resulting call stack

``````m(arr, low: 2, high: 1, num: 14)     mid: 1  returns 2
m(arr, low: 2, high: 2, num: 14)     mid: 2  returns 2
m(arr, low: 0, high: 2, num: 14)     mid: 1  returns 2
m(arr, low: 0, high: 7, num: 14)2    mid: 3
``````

## Step 8: Back in `mystery(0, 7, 14)`

• Back in `mystery(0, 7, 14)`
• Finished `call 2`, got back `2`
• Stops and returns `2`

### Resulting call stack

``````m(arr, low: 2, high: 1, num: 14)     mid: 1  returns 2
m(arr, low: 2, high: 2, num: 14)     mid: 2  returns 2
m(arr, low: 0, high: 2, num: 14)     mid: 1  returns 2
m(arr, low: 0, high: 7, num: 14)     mid: 3  returns 2
``````

As mentioned in Step 5, the question asks how many calls are made, not what the initial call returns. Four calls are made.

This variant of binary search returns the insertion point if the key is not found. The insertion point is where the key would go if it were to be inserted into the array. See binary search for additional discussion of this and other variants.