none
O(log(n)) find the number RRS feed

  • Question

  • need help with this one .

    You are given an array of numbers nums and an integer 𝑥. We know that
    nums is sorted in increasing order. You need to determine, in O(log(n))
    time (n is the size of the array) if the number 𝑥 exists in the array. Return
    "Yes if nums contains 𝑥 and "No"otherwise.

    this is my Code and it's not working.  How can I fix it?

     static void Main(string[] args)
            {
                int[] array = new int[] { 10, 11, 12, 13, 14, 20, 60, 90, 100 , 102, 105, 114, 41026 };
                int x = 14;
                int left = 0;
                int right = array.Length - 1;
                int mid = 0;


                while (left <= right)
                {

                    if (x > array[right] || x < array[left])

                    {
                        Console.WriteLine("No");
                        break;
                    }

                    mid = (left + right) / 2;

                    if (array[mid] > x)
                    {
                        right = mid - 1;
                    }
                    else if (array[mid] < x)
                    {
                        left = mid + 1;

                    }
                    else if (array[mid] == x)
                    {
                        Console.WriteLine("yes");
                        break;
                    }


                     if (array[mid] != x)

                        Console.WriteLine("No");
                }



                Console.ReadKey();

            }
        }
    }

    Monday, April 9, 2018 9:38 PM

Answers

  • Get rid of the test at the end.

                    else if (array[mid] == x)
                    {
                        Console.WriteLine("yes");
                        break;
                    }
    
    
                     // Remove these lines.
                     //if (array[mid] != x)
    
                     //   Console.WriteLine("No");
                }

    • Proposed as answer by Fei HuModerator Tuesday, April 10, 2018 2:16 AM
    • Marked as answer by Krishtikri Tuesday, April 10, 2018 4:49 AM
    Monday, April 9, 2018 11:22 PM

All replies

  • Get rid of the test at the end.

                    else if (array[mid] == x)
                    {
                        Console.WriteLine("yes");
                        break;
                    }
    
    
                     // Remove these lines.
                     //if (array[mid] != x)
    
                     //   Console.WriteLine("No");
                }

    • Proposed as answer by Fei HuModerator Tuesday, April 10, 2018 2:16 AM
    • Marked as answer by Krishtikri Tuesday, April 10, 2018 4:49 AM
    Monday, April 9, 2018 11:22 PM
  • Hello Krishtikri,

    Try to remove the last condition as below code.

     while (left <= right)
                {
                    int mid = (left + right) / 2;
                    if (array[mid] > x) right = mid - 1;
                    else if (array[mid] < x) left = mid + 1;
                    else { Console.WriteLine("Yes");break; };
                }

    Best Regards,

    Neil Hu


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Tuesday, April 10, 2018 2:16 AM
    Moderator
  • Thank you very much!
    Tuesday, April 10, 2018 4:50 AM
  • thank you very much
    Tuesday, April 10, 2018 4:54 AM
  • Now it is works, but sill can't understand, how it works , when x=25, because the condition  if (x > array[right] || x < array[left]) is not true, 

    Tuesday, April 10, 2018 5:06 AM
  • Yes it is. At the critical point, right=5, so array[5]=20, so 25 > 20.
    Tuesday, April 10, 2018 5:13 AM
  • oooh, now I see , thank you :)
    Tuesday, April 10, 2018 5:34 AM