Skip to content

Instantly share code, notes, and snippets.

@XcqRomance
Created November 13, 2018 14:14
Show Gist options
  • Save XcqRomance/35fe6bb32c12e618f01aae3adcceb839 to your computer and use it in GitHub Desktop.
Save XcqRomance/35fe6bb32c12e618f01aae3adcceb839 to your computer and use it in GitHub Desktop.
二分查找实现代码 注意点:1.循环退出条件low<=high而不是low<high;2.mid的取值,mid = (low + high) / 2;可能溢出,改进方法:mid = low + (high - low) / 2,极致优化,位运算:mid = low + ((high - low) >>1);3.low和high的更新
int bsearch(int[] a, int n, int value) {
int low = 0;
int high = n - 1;
while (low <= high) {
int mid = low + ((high - low) >>1);
if (a[mid] == value) {
return mid;
} else if (a[mid] < value) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment