1. ๆพๆจก็ณๅผ first or last occurrence, ไบๅๆณ
see leetcode 34
int left = 0;
int right = nums.length - 1;
// find first occurrence
while (left < right) {
int mid = left + (right - left)/2;
if (nums[mid] < target) { // ๅพๅณๅ้จๆพ
left = mid + 1;
} else { // ๅพๅทฆๅ้จๆพ
right = mid;
}
}
return left; // right
// find last occurrence
while (left < right) {
int mid = left + (right - left + 1)/2; // notice! +1
if (nums[mid] > target) { // ๅพๅทฆๅ้จๆพ
right = mid - 1;
} else { // ๅพๅณๅ้จๆพ
left = mid;
}
}
return left;
2. ๆพ็ขบๅๅผ, ไธๅๆณ, template,
left, right = 0, len(array) - 1
while left <= right:
// (left + right) >>> 1 is best!
mid = (left + right) >>> 1 // left + (right - left) / 2
if array[mid] == target:
# find the target!!
break or return result
elif array[mid] < target:
left = mid + 1
else:
right = mid - 1
when do you use while (start < end) , when do you use while (start <= end) ?
You use while (start <= end) if you are returning the match from inside the loop.
You use while (start < end) if you want to exit out of the loop first, and then use the result of start or end to return the match.
