首页 > 代码库 > binary search完整笔记
binary search完整笔记
1 Search in Rotated Sorted Array
二分搜索，注意分清各种情况
1 public class Solution { 2 public int search(int[] nums, int target) { 3 int i = 0, j = nums.length - 1; 4 while (i + 1 < j) { 5 int mid = i + (j - i) / 2; 6 if (nums[mid] == target) { 7 return mid; 8 } 9 10 if (nums[mid] < target) {11 if (target >= nums[i] && nums[mid] <= nums[i]) {12 j = mid;13 } else {14 i = mid;15 }16 } else {17 if (target <= nums[j] && nums[mid] >= nums[j]) {18 i = mid;19 } else {20 j = mid;21 }22 }23 24 }25 if (nums[i] == target) {26 return i;27 }28 if (nums[j] == target) {29 return j;30 }31 return -1;32 }33 }
这种方法在只有一边出现的时候容易出bug，target > mid 在对比的时候target和mid都统一用num[i]做比较，target < mid 时用num[j]
九章的方式，区分mid在左边还是右边，然后再做判断，合理简单很多，代码如下：
1 public class Solution { 2 public int search(int[] A, int target) { 3 if (A == null || A.length == 0) { 4 return -1; 5 } 6 7 int start = 0; 8 int end = A.length - 1; 9 int mid;10 11 while (start + 1 < end) {12 mid = start + (end - start) / 2;13 if (A[mid] == target) {14 return mid;15 }16 if (A[start] < A[mid]) {17 // situation 1, red line18 if (A[start] <= target && target <= A[mid]) {19 end = mid;20 } else {21 start = mid;22 }23 } else {24 // situation 2, green line25 if (A[mid] <= target && target <= A[end]) {26 start = mid;27 } else {28 end = mid;29 }30 }31 } // while32 33 if (A[start] == target) {34 return start;35 }36 if (A[end] == target) {37 return end;38 }39 return -1;40 }41 }
binary search完整笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。