This simple code should not Accepted, but it is Accepted.


  • 0
    0
    class Solution {
    public:
        int search(int A[], int n, int target) {
            for (int i = 0; i < n; ++i) {
                if (A[i] == target) {
                    return i;
                }
            }
            return -1;
        }
    };

  • 1
    J

    That is a valid solution but it is O(n). The problem was asking more for a O(log n) solution with binary search.


  • 0
    0

    So, I think, there should be other test cases to check time complexity.


  • 0
    S

    OJ doesn't analyze the time comlexity, but rather relies on a hard time limit to decide if the program is acceptable. However, the difference between O(logn) and O(n) are usually not big enough for a single threshold to separate them, unless we use a very, very big test cases that exceed the capability of OJ. So please use your own discretion when writing programs like this.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.