直接遍历:
public int search (int[] nums, int target) { for (int i=0;i<nums.length;i++){ if(target == nums[i]) return i; } return -1; }
运行时间:32ms
超过55.72% 用Java提交的代码
占用内存:12260KB
超过37.98%用Java提交的代码
二分查找,略微优化版本:
public int search(int[] nums, int target) { if(nums == null || nums.length == 0) return -1; if(nums.length == 1) { if(nums[0] == target) return 0; else return -1; }else { int pos = 0; // 查找位置 for (; pos < nums.length - 1; pos++) { if (target == nums[pos]) return pos; if (nums[pos] > nums[pos + 1]) break; } int resu1 = binarySearch(nums, 0, pos, target); int resu2 = binarySearch(nums, pos + 1, nums.length - 1, target); return resu1 == -1 ? resu2 : resu1; } } private int binarySearch(int[] nums, int left, int right, int target) { while(left <= right){ int mid = (left + right) / 2; if(nums[mid] > target) right = mid - 1; else if(nums[mid] < target) left = mid + 1; else{ return mid; } } return -1; }
运行时间:36ms
超过17.15% 用Java提交的代码
占用内存:12128KB
超过69.17%用Java提交的代码