1. Search in Rotated Sorted Array（33.leetcode）
- 当 选择 right= nums.length -1 时， while loop 的终止 会是 left < right , 而不是 while(left <= right)
- 解题思路： 只找 连续 increasing 的区间，
public int search(int[] nums, int target) {
int left = 0, right = nums.length -1;
while( left < right ){
int mid = left + (right - left) / 2;
if(nums[mid] == target) return true;
else if( nums[mid] >= nums[left]){
if( target < nums[mid] && target >= nums[left] ) right = mid - 1;
else left = mid + 1;
}
else { // nums[left] >= nums[mid]
if( target <= nums[ right] && target > nums[mid] ) left = mid - 1;
else right = mid + 1;
}
}
return nums[left] == target ? left : -1;
}
2. Search in Rotated Sorted Array II（81.leetcode）
- rotated sorted array + duplicate
- 出现duplicate 后， 会导致的 （left > mid ? ）无法判断连续ascending 的区间，
- 解题办法： 去重 ， 把pointer 移动到 和mid element 不一样的element 上
public boolean search(int[] nums, int target) {
int left = 0 , right = nums.length - 1;
while( left <= right){
int mid = left + (right - left)/2;
if( nums[mid] == target) return true;
if( nums[left] == nums[mid]) left ++;
else if( nums[left] < nums[mid]) {
if( target >= nums[left] && target < nums[mid] ) right = mid -1 ;
else left = mid + 1;
}else{ // nums[left] > nums[mid]
if( target <= nums[right] && target > nums[mid]) left = mid + 1;
else right = mid - 1;
}
} // while
return false;
}
3. Find Minimum in Rotated Sorted Array（153.leetcode）
public int findMin(int[] num) {
if(num == null || nums.length == 0) return 0;
intleft = 0, right = num.length - 1;
while( left < right ){
int mid = left + (rigth - left)/2;
if(num[mid] < num[right]) right = mid;
else if( num[mid] > num[right]) // min in the right part
left = mid - 1;
}
return num[left];
}
4.Search Insert Position（ 35.leetcode）
public int searchInsert(int[] nums, int target) {
if(num == null || num.length == 0) reutn 0;
int left = 0, right = num.length - 1;
while( left <= right ){
int mid = left + (right - left)/2;
if( num[ mid] == target) return mid;
if(num[ mid] < target ) left = mid + 1;
else if ( num[mid] > target) right = mid - 1;
}
return left;
}
5.Two Sum II - Input array is sorted（278.leetcode）
public int firstBadVersion(int n) {
int start = 1, end = n;
while (start < end) {
int mid = start + (end-start) / 2;
if (!isBadVersion(mid)) start = mid + 1;
else end = mid;
}
return start;
}
6. Intersection of Two Arrays II (350.leetcode）
-**解题思路： ** 要比较2个array 的话， 各用一个pointer
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] res = new int[ Math.max( nums1.length , nums2.length)];
int left = 0, right = 0, used = 0;
while( left < nums1.length && right < nums2.length ){
if( nums1[left] == nums2[right]){
left ++, right ++;
res[used ++] = nums1[left];
}
else if( nums1[left] < nums2[right]) left ++;
else right ++:
}
return Arrays.copyOf(ans, used);
}
