# Binary Search On Sorted Numbers

Itâ€™s easiest to show a binary search on numbers using pseudo-code

```int array[1000] = { sorted list of numbers };
int N = 100;  // number of entries in search space;
int high, low, mid; // our temporaries
int x; // value to search for

low = 0;
high = N -1;
while(low < high)
{
mid = (low + high)/2;
if(array[mid] < x)
low = mid + 1;
else
high = mid;
}
if(array[low] == x)
// found, index is low
else
// not found```

Do not attempt to return early by comparing array[mid] to x for equality. The extra comparison can only slow the code down. Note you need to add one to low to avoid becoming trapped by integer division always rounding down.

Interestingly, the above version of binary search allows you to find the smallest occurrence of x in the array. If the array contains duplicates of x, the algorithm can be modified slightly in order for it to return the largest occurrence of x by simply adding to the if conditional:

```while(low < high)
{
mid = low + ((high - low) / 2);
if(array[mid] < x || (array[mid] == x && array[mid + 1] == x))
low = mid + 1;
else
high = mid;
}```

Note that instead of doing `mid = (low + high) / 2`, it may also be a good idea to try `mid = low + ((high - low) / 2)` for implementations such as Java implementations to lower the risk of getting an overflow for really large inputs.

Feedback about page:

Feedback:
Optional: your email if you want me to get back to you:

Table Of Contents