# Binary Search On Sorted Numbers

suggest changeItâ€™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.