登录
  • #刷题
  • #leetcode

Search in Rotated Sorted Array有个测试老通不过

TonyJang
1033
2
测试数组是{4,5,6,7,0,1,2},想查找8让函数返回-1,但是老显示time out咋回事啊?
[br][/br][br][/br]public class SearchinRotatedSortedArray {[br][/br][br][/br]    public static int search(int[] A, int target) {[br][br][/br]		// 以下是binary search九章算法的模板[br][/br][br][/br]		int start = 0;[br][/br][br][/br]		int end = A.length - 1;[br][/br][br][/br]		int mid;[br][/br][br][/br]		while (start <= end) {[br][/br][br][/br]			mid = start + (end - start) / 2;[br][/br][br][/br]			if (A[mid] == target) {[br][/br][br][/br]				return mid;[br][/br][br][/br]			}[br][/br][br][/br]			// 情况1 Astart比Amid小 说明mid在前半段[br][/br][br][/br]			if (A[start] < A[mid]) {[br][/br][br][/br]				// 如果进下一个if循环说明target在第一段且在start和mid之间[br][/br][br][/br]				// 在前四分之一[br][/br][br][/br]				if (A[start] <= target && target <= A[mid]) {[br][/br][br][/br]					end = mid;[br][/br][br][/br]				} else {// 说明target小于start或者大于mid  总之在后四分之三[br][/br][br][/br]					start = mid;[br][/br][br][/br]				}[br][/br][br][/br]			} else {// 这里打else的情况 说明A[start]大于A[mid] A[mid]在后半段[br][/br][br][/br]				if (A[mid] <= target && target <= A[end]) { // 说明A在后半段的后半段[br][/br][br][/br]															// mid和end之间[br][/br][br][/br]					start = mid;// 后四分之一[br][/br][br][/br]				} else {[br][/br][br][/br]					end = mid; // 在前四分之三[br][/br][br][/br]				}[br][/br][br][/br]			}[br][/br][br][/br]		}[br][/br][br][/br]		[br][/br][br][/br]		return -1;[br][/br][br][/br]	}[br][/br][br][/br]    public static void main(String[] args){[br][br][/br]        [br][/br][br][/br]        int[] a={4,5,6,7,0,1,2};[br][br][/br]        System.out.println(search(a,8));[br][/br][br][/br]        [br][/br][br][/br]        [br][/br][br][/br]    }[br][/br][br][/br]}[br][/br][br][/br]
2条回复
热度排序

发表回复