I am developing an algorithm to find the chromatic number of a graph. I use a genetic algorithm in order to determine whether the graph can be colored using p colors. I determine p using a binary search. The lower boundary of my binary search is 1 and the upper boundary according to Brooks' theorem is the degree of the graph plus one. As I know, the possibility of a number to be the answer is not evenly distributed, thus I cannot use the middle of the interval every time. So how can I determine the median point in an optimal way?
Thank you in advance!!!