Почему не работает бинарный поиск?

Question

[daniel1]

Здравствуйте, у меня возникла проблема - не работает бинарный поиск. А если точнее, то работает не со всеми значениями. Если искать цифру 6 например, то программа уходит в бесконечный цикл.

static void Main(string[] args)
        {
            int[] A = { 1, 3, 5, 6, 8, 9, 10, 24, 100, 156 };
          
            
            Console.WriteLine(BinarySearch(A, A.Length, 6));
            Console.Read();
        }
        
        static int BinarySearch(int[] A,int n,int x)
        {
            int p = 1;
            int r = n;
            while(p<=r)
            {
                int q = (p + r) / 2;
                if(A[q]==x)
                {
                    return q;
                }
                if(A[q]>x)
                {
                    r = q - 1;
                }
                if(A[q]<x)
                {
                    r = q + 1;
                }
            }
            return -1;
        }

Comments

[Андрей Вершинин]

Если исправлять Вашу программу, то вначале int p = 0;, и потом не r = q + 1, а p = q + 1.

Answer 1

[Андрей Вершинин]

Странный он у вас какой-то.
Правильно так:

static int BinarySearch(int[] A, int n, int x)
{	
	int left_bound = 0, right_bound = n, q;

	while(left_bound != right_bound)
	{
		q = (left_bound + right_bound) >> 1;
		
		if(A[q] == x)
		    return q;
		else if(A[q] > x)
		    right_bound = q;
		else
		    left_bound = q;
	}

	return -1;
}