My simple binary search solution


  • 0
    H
    public class Solution {
        public int search(int[] A, int target) {
            int i =0;
            for (i = 0; i < A.length-1; i++){
                if (A[i] >A[i+1])
                    break;
            }
            
            int s1 = binarySearch(A,0,i,target);
            int s2 = binarySearch(A,i+1,A.length-1,target);
            
            if (s1 != -1)
                return s1;
            if (s2 != -1)
                return s2;
            return -1;
        }
        
        public int binarySearch(int[] A, int lower, int upper,int target){
            int mid;
            while (lower <= upper){
                mid = (lower+upper)/2;
                if (A[mid] == target)
                    return mid;
                else if (A[mid] < target){
                    lower = mid+1;
                }else{
                    upper = mid-1;
                }
            }
            return -1;
        }
    }

  • 0
    J

    Your solution works linear time at the worst case. Take a look at first loop of your search function.

    Hint: you can find your "i" by modified binary search as well.


  • 0
    H

    It will be better if you can find i by binary search


  • 0
    B

    This is a O(N) solution I think, because the worst case of finding i is oN


Log in to reply
 

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