I don't understand all these discussions and AC codes.


  • -1
    Y

    Since we all know that the worst case is O(n). Why are you still trying to show some binary-like algorithm?

    Just linear search!

    public class Solution {
        public boolean search(int[] A, int target) {
            for(int i=0;i<A.length;i++){
                if(A[i] == target) return true;
            }
            return false;
        }
    }
    

    This got accepted. LOL


  • 15
    S

    This logic is exactly like saying "Quicksort has a worst time complexity of O(n^2), so why bother using it? Let's just stick with Bubble sort". "Worst cast time complexity" is just one way to evaluate an algorithm. In practice, we usually care more about 'amortized time', where the frequencies of the appearance of the costly inputs are taken into consideration. This problem degenerates to O(n) problem under only one case (num[start] = num[mid] = num[end]), for most other cases, the binary search still works. So the amortized time for this algorithm is still O(logN). You cannot just deny the entire algorithm just because of one edge case it can't handle well.


Log in to reply
 

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