Java solution with comments


  • 0
    W
    // 思路: 二分查找变异
    // 无论怎样二分数组,左右两个数组至少有一个是有序的
    public boolean search(int[] A, int target) {
    	int begin = 0, end = A.length - 1;
    	while (begin <= end) {
    		int mid = begin + (end - begin) / 2;
    		if (A[mid] == target)
    			return true;
    		if (A[mid] > A[end]) { // 左前半部分有序
    			if (A[begin] <= target && target < A[mid]) { // 落在左半部分查找
    				end = mid - 1; //
    			} else {
    				begin = mid + 1;
    			}
    		} else if (A[mid] < A[end]) { // 右半部分有序
    			if (A[mid] < target && target <= A[end]) { // 落在右半部分查找
    				begin = mid + 1;
    			} else {
    				end = mid - 1;
    			}
    		} else {
    			// A[mid] == A[end]
    			end--; // 无法判断,则让end--。后面继续处理,毕竟有A[mid]==A[end],end--不影响查找结果
    		}
    	}
    
    	return false;
    }

  • 0
    M

    Thanks for sharing.

    But regarding the, "if (A[mid] > A[end])" (left half sorted),
    can you explain a little, why "if( A[mid] > A[begin] )" doesn't work?
    I'm quite confused about this point.


Log in to reply
 

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