首页 > 代码库 > 数据结构——二分搜索

数据结构——二分搜索

递归实现

/** * 二分搜索(递归实现) * @param A     待搜索数组 * @param num   搜索值 * @param left  区间左指针 * @param right 区间右指针 * @param mid   基准 */private static void search(int[] A, int num, int left, int right, int mid) {    if (A[mid] == num) { // 如果找到要找的数,记录其下标        res = mid;    }    if (left >= right)        return ;    if (A[mid] >= num) { // 出现在左边        right = mid - 1;        mid = left + (right-left)/2;        search(A, num, left, right, mid);    }    if (A[mid] < num) { // 出现在右边        left = mid + 1;        mid = left + (right-left)/2;        search(A, num, left, right, mid);    }}

非递归实现

/** * 二分搜索(非递归实现) * @param A     带搜索数组 * @param n     数组长度 * @param num   搜索值 * @return */private static int search2(int[] A, int n, int num) {    int left = 0;    int right = n - 1;    int res = -1;    while (left <= right) {        int mid = left + (right - left)/2;        if (A[mid] == num) {            res = mid;            right = mid - 1;        }        if (A[mid] >= num) { // 左区间            right = mid - 1;        } else {            left = mid + 1;        }    }    return res;}private static int search3(int[] arr, int n, int num) {    int left = 0;    int right = n-1;    while (left <= right) {        int mid = left + ((right-left)>>1);        if (arr[mid] > num) {            right = mid-1;        }else if (arr[mid] < num) {            left = mid+1;        }else {            return mid;        }    }    return -1;}

数据结构——二分搜索