Simple C++ Solution using Binary Search Without Recursion


  • 2
    C
    class Solution {
    public:
        int search(int A[], int n, int target) {
            if(n==0)
                return -1;
            int left = 0;
            int right = n-1;
            int middle = 0;
            while(left<=right){
                middle = left+(right-left)/2;
                if(A[middle]==target)
                    return middle;
                if(A[middle]>=A[left]){
                    if(A[left]<=target&&target<A[middle]){
                        right = middle-1;
                    }
                    else
                        left = middle+1;
                }
                else{
                    if(A[middle]<target&&target<=A[right]){
                        left = middle+1;
                    }
                    else
                        right = middle-1;
                }
            }
            return -1;
        }
    };
    

    The key point to solve this problem is judge which side of the array is sorted.

    If A[middle]>A[left],this means the left side is sorted.

    So if target>A[left] and <A[middle],we can make sure this target is in the [left,middle],we should search the left side.
    Otherwise,we should search the right side.


Log in to reply
 

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