对于二分搜索区间有两种形式,一种是左闭右开,一种是左闭右闭,区别在于初始右边界的赋值,如果是:right = arr.length 显然是左闭右开,而right=arr.length-1则为左闭右闭,两种区间选择不同导致后续缩小搜索区间也有不同的形式。
需要注意的是, 循环体外的初始化条件,与循环体内的迭代步骤, 都必须遵守一致的区间规则
int search1(int array[], int n, int v) { int left, right, middle; left = 0, right = n - 1; while (left <= right) { middle = (left + right) / 2; if (array[middle] > v) { right = middle - 1; //[left,mid-1]保持区间一致 } else if (array[middle] < v) { left = middle + 1; } else { return middle; } } return -1; } int search2(int array[], int n, int v) { int left, right, middle; left = 0, right = n; while (left < right) //没有等号 { middle = (left + right) / 2; if (array[middle] > v) { right = middle; //区间[left,mid)保持一致 } else if (array[middle] < v) { left = middle + 1; } else { return middle; } } return -1; }
二分查找在面对有序数组时,能够极大减少搜索次数,对于二分查找典型的应用有:
citations[i] >= lenght-i
的有区间长度public int hIndex(int[] citations) { int l = 0; int r = citations.length - 1; while (r >= l) { int m = l + r >> 1; if (citations[m] == citations.length - m) { return citations[m]; } else if (citations[m] > citations.length - m){ r = m - 1; } else l=m+1; } return l; }
一点反思:需要注意边界情况,如为空、为1
public int hIndex(int[] citations) { int l = 0; int r = citations.length - 1; while (r >= l) { int m = l + r >> 1; if (citations[m] == citations.length - m) { return citations[m]; } else if (citations[m] > citations.length - m) { r = m - 1; } else l = m + 1; } return citations.length - l; }