My algorithm using binary search is accepted.Want some suggestions as it has a lot of if-else.


  • 3
    W

    I want to use binary search without locating the rotate number, and this is my code.My algorithm contains so many If-Else, so please help me to improve my code making it more understandable and concise.

     class Solution {
        public:
            int search(int A[], int n, int target) {
                int index=-1;
                if(n!=0){
                    int first=0,last=n-1;
                    while(first<=last){
                        int mid=(first+last)/2;
                        if(A[mid]==target){
                            index=mid;
                            break;
                        }
                        else if(A[mid]>target){
                            if(A[mid]>=A[first]){
                                if(target<A[first]){
                                    first=mid+1;
                                }
                                else if(target>A[first]){
                                    last=mid-1;
                                }
                                else{
                                    index=first;
                                    break;
                                }
                            }
                            else{
                                last=mid-1;
                            }
                        }
                        else{
                            if(A[mid]>=A[last]){
                                first=mid+1;
                            }
                            else{
                                if(target<A[last]){
                                    first=mid+1;
                                }
                                else if(target>A[last]){
                                    last=mid-1;
                                }
                                else{
                                    index=last;
                                    break;
                                }
                            }
                        }
                    }
                }
                return index;
            }
        };

  • 9
    S

    Your code is really difficult to understand and must have taken you a lot of brain work to use so many nested loops ,however I can suggest you a different approach.
    say your array is 0,1,2,3,4,5 if it is rotated to say 4,5,0,1,2,3 then you first find a pivot ,pivot is the index of the number which is greater than another e.g 5 is the element greater than0 so pivot is index of 5 ie 1

    STEPS:

    1. Find out pivot point and divide the array in two
      sub-arrays.

    2. Now call binary search for one of the two sub-arrays.
      (a) If element is greater than 0th element then
      search in left array
      (b) Else Search in right array

    3. If element is found in selected sub-array then return index
      Else return -1.
      and yes duplicates are not handled using this ,but question makes assumption that we don't have any duplicates

      class Solution {
      public:
      int findpivot(int A[], int low , int high){

          if(high < low)
          return -1;
          if(high == low)
          return low;
          int mid = low + (high - low )/2;
          if(A[mid] > A[mid+1] && mid < high)
          return mid;
          else
          if(A[mid] < A[mid-1] && mid > low)
          return mid - 1;
         
          else if(A[low] >= A[mid])
          findpivot(A, low, mid-1);
           else 
          findpivot(A, mid+1, high);
          
      }
      int binarysearch(int A[], int low, int high, int target){
          int mid = low + (high - low)/2;
          
          if(high<low)
          return -1;
          if(A[mid] == target)
          return mid;
          else
          if(A[mid] < target)
          return binarysearch(A, mid+1, high, target);
          else
          return binarysearch(A, low, mid-1, target);
          
      }
      int search(int A[], int n, int target) {
          int pivot = findpivot(A, 0, n-1);
          if(pivot == -1)
          return binarysearch(A , 0 , n-1,target);
          if(A[pivot] == target)
          return pivot;
          else 
          if(A[0] <= target)
          return binarysearch(A, 0, pivot-1, target);
          else
          return binarysearch(A, pivot+1, n-1, target);
          
      }
      

      };


  • 0
    W

    A well understanding algorithm! Thank you for your help. Your method I have ever thought, it is true that finding the pivot can make it easy. Well, I think using binary search without locating the pivot can have a better version than mine.


  • 0
    H

    I think the problem is just aimed to practice classifying conditions... so the if else cannot be simplified any better may be use recursive looks more concise? also we can merge some condition in the codes

    int search(int A[], int left, int right, int x)
    {
        if (left > right)
            return -1;
        
        int mid = (left + right) >> 1;
        if (x == A[mid])
            return mid;
        else if (x < A[mid])
        {
            if (A[mid] >= A[left])
            {
                if (x >= A[left])
                    return search(A, left, mid - 1, x);
                else
                    return search(A, mid + 1, right, x);
            }
            return search(A, left, mid - 1, x);
        }
        else
        {
            if (A[mid] < A[left])
            {
                if (x >= A[left])
                    return search(A, left, mid - 1, x);
                else
                    return search(A, mid + 1, right, x);
            }
            return search(A, mid + 1, right, x);
        }
    }
    
    int search(int A[], int n, int target) {
        return search(A, 0, n - 1, target);
    }

  • 4
    M

    I agree with swapedoc's thought. Find the pivot(The smallest number or the biggest number, I choose the small one) first then we can divide the array into two part. The rest is do the simple binary search.

    public class Solution {
        public int search(int[] A, int target) {
            int start, end;
            int pivot = findPivot(A);
            if (target > A[A.length - 1]) {
                start = 0;
                end = pivot - 1;
            } else {
                start = pivot;
                end = A.length - 1;
            }
            while (start <= end) {
                int mid = (start + end) / 2;
                if (A[mid] < target) {
                    start = mid + 1;
                } else if (A[mid] > target) {
                    end = mid - 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }
        
        public int findPivot(int[] A) {
        	int start = 0;
        	int end = A.length - 1;
        	if (A[end] >= A[start]) {
        	    return 0;
        	} // in case the array is not rotated.
        	while (start <= end) {
        		int mid = (start + end) / 2;
        		if (A[mid] > A[start]) {
        			start = mid ;
        		} else if (A[mid] < A[start]){
        			end = mid;
        		} else {
        			return end;
        		}
        	}
        	return end ;
        }
    }
    

    Or you can just do it in your way, I found a much easier code on the Internet :

    Hope it can help you.

    public class Solution {
        public int search(int[] A, int target) {
            int start = 0;
            int end = A.length - 1;
            int mid;
            
            while (start + 1 < end) {
                mid = start + (end - start) / 2;
                if (A[mid] == target) {
                    return mid;
                }
                if (A[start] < A[mid]) {
                    // situation 1, red line
                    if (A[start] <= target && target <= A[mid]) {
                        end = mid;
                    } else {
                        start = mid;
                    }
                } else {
                    // situation 2, green line
                    if (A[mid] <= target && target <= A[end]) {
                        start = mid;
                    } else {
                        end = mid;
                    }
                }
            } // while
            
            if (A[start] == target) {
                return start;
            }
            if (A[end] == target) {
                return end;
            }
            return -1;
        }
    }

  • 0
    W

    Thanks about your help! Well methods using divide and conquer


  • 0
    W

    Yeah! Really helpful,I think it's pretty concise.Here,I also found a good algorithm in the old discuss


  • 2
    W

    My python code also use binary search to find the pivot and search the result and only use 3 if statements.

    class Solution:
    #return largest index satisfy criteria f, Assuming all those satisfy f located before those not satisfy f.
    def bsearch(self, n, f):
        low,high=0,n
        if not f(low):
            return -1
        while high - low > 1:
            mid = (low+high)/2
            if f(mid):
                low = mid
            else:
                high = mid
        return low
    
    def search(self, A, target):
        n = len(A)
        # pivot point to the minimum number
        pivot = (self.bsearch(n,lambda i:A[i] >= A[0]) + 1) % n
        i=self.bsearch(n, lambda i:A[(i + pivot)%n] <= target)
        return (i+pivot)%n if i >= 0 and A[(i+pivot)%n] == target else -1
    

  • 39
    S

    Here is my Java solution, mostly copied from @martin5678 's answer but a little more optimized.

    public int search(int[] A, int target) {
    	// check if the target is in the sorted part, if so keep doing the binary search
    	// otherwise throw away the sorted part and do the same on the other part of the array
    	int start = 0;
    	int end = A.length-1;
    	
    	while (start <= end) {
    		int mid = (start + end) / 2;
    		if (A[mid] == target) return mid;
    		if (A[start] <= A[mid]) {
    			// situation 1, red line
    			if (A[start] <= target && target <= A[mid]) {
    				end = mid-1;
    			}
    			else {
    				start = mid+1;
    			}
    		}
    		else {
    			// situation 2, green line
    			if (A[mid] <= target && target <= A[end]) {
    				start = mid+1;
    			}
    			else {
    				end = mid-1;
    			}
    		}
    	}
    	return -1;		
    }

  • 0
    Z
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 3
    Z

    here is my recursive solution and some comments based on Binary Search, in Java.

    the key idea is: compare the left/right most point with mid-point, if A[mid] > A[left], the left half of this array must be in increasing order (even if we do not know how many elements are shifted of this array). then, we decide whether the target value is in the range of the increasing half of this subarray.

    based on this idea, we will see that the rotation pivot index is not necessary to know. it's basically the same as Binary Search, and have the same time complexity.

    public int search(int[] A, int target) {
        int n = A.length;
        return search(A, 0, n - 1, target);
    }
    
    private int search(int[] a, int s, int e, int target) { // array,start index,end index, target
        // base case
        if (s > e) {
            return -1;
        }
        int mid = (s + e) / 2;
        if (a[mid] == target)
            return mid;
    
        if (a[mid] >= a[s]) {  
        // it means the left half of array is in increasing order. so if the target is in the range of 
        // left half, it's the same as typical binary search (even though rotate pivot is still a mistery)
        // binary search recursively and finally get a index that a[index] == target, or -1 if not found
            if (target < a[mid] && target >= a[s]) {
                return search(a, s, mid - 1, target);
            } else {
                return search(a, mid + 1, e, target);
            }
        } else {
            if (target <= a[e] && target > a[mid]) {
                return search(a, mid + 1, e, target);
            } else {
                return search(a, s, mid - 1, target);
            }
        }
    }
    

    PS: because every time, we reduce the search range by half, so the time complexity is O( logn)


  • 0
    W

    There are 4 cases: 1. A[mid] == result; found. 2. A[mid] > target && A[mid] < A[e], result has to be on left side. 3. A[mid] < target && A[mid] > A[e], result has to be on right side. 4. all the other cases, we need to search on both sides.

    class Solution {
        int halfingSearch(int A[], int s, int e, int target){
            int res = -1;
            if(s > e)
                return res;
            
            int mid = (s+e)/2;
            if(A[mid] == target){
                res = mid;
            }else if(A[mid] > target && A[mid] < A[e]){
                res = halfingSearch(A, s, mid-1, target);
            }else if(A[mid] < target && A[mid] > A[e]){
                res = halfingSearch(A, mid +1, e, target);
            }else{
                //search on both sides
                res = halfingSearch(A, s, mid-1, target);
                if(res == -1)
                    res =halfingSearch(A, mid+1, e, target);    
            }
            return res;
        }
    public:
        int search(int A[], int n, int target) {
            return halfingSearch(A, 0, n-1, target);
        }
    };

  • -1
    R
    This post is deleted!

  • 0
    W

    You are right! It is forward idea without finding pivot. Draw a axis, there are three cases
    target>A[n/2]>A[0], A[n/2]>A[0]>target...Then
    class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return an integer
    def search(self, A, target):
    n=len(A)
    if n==0:
    return -1
    elif n==1:
    if A[0]==target:
    return 0
    else:
    return -1
    elif n==2:
    if A[0]==target:
    return 0
    elif A[1]==target:
    return 1
    else:
    return -1

        else:
            if A[n/2]==target:
                return n/2
            elif target>A[n/2]>A[0] or A[n/2]>A[0]>target:
                if self.search(A[n/2+1:],target)==-1:
                    return -1
                else:
                    return n/2+1+self.search(A[n/2+1:],target)
            elif A[n/2]>target>=A[0]:
                return self.search(A[:n/2],target)
    
    
            elif A[n/2]<A[0]<=target or target<A[n/2]<A[0]:
                return self.search(A[:n/2],target)
    
            elif A[n/2]<target<A[0]:
                if self.search(A[n/2+1:],target)==-1:
                    return -1
                else:
                    return n/2+1+self.search(A[n/2+1:],target) 

  • 0
    X

    An iterative solution. I listed all situations where we should pick the left half of the range.

    public class Solution {
        public int search(int[] A, int target) {
            int low = 0, high = A.length-1, mid = -1;
            while(low <= high) {
                mid = low + (high-low)/2;
                if (A[mid] == target) {
                    return mid;
                } else if (A[low] == target) {
                    return low;
                } else if (A[high] == target) {
                    return high;
                } else if ( (A[low] < A[high] && target < A[mid]) || 
                            (A[low] > A[high] && 
                                ((A[mid] > A[low] && target < A[mid] && target > A[low]) || 
                                 (A[mid] < A[low] && (target > A[low] || target < A[mid]))))) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }
    }

  • -3
    A

    Here is my AC code. Pretty simple and clear.

    public int search(int[] A, int target) {
        for(int i = 0; i < A.length; i++) {
            if (target == A[i]) return i;
            else if (target < A[i]) {
                for (int j = A.length - 1; j >= 0; j--) {
                    if (target == A[j]) return j;
                    else if (target > A[j]) return -1;
                }
                return -1;
            }
        }
        return -1;
    }

  • 0
    S

    Have you ever read other sharing solutions? The best one should be O(log N). This code is O(N) though.


  • 0
    A

    @sean hyuntaek Can you tell me the time complexity of your solution?
    Is it better than O(n)?


  • 0
    H

    my code is more clear then :)

    public int search(int[] A, int target) {
    for(int i = 0; i < A.length; i++)
    if (target == A[i]) return i;
    return -1;
    }


Log in to reply
 

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