二分法在有序数组中的应用(Java&C)

在有序数组中确定num是否存在

Java实现

public static boolean exist(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return false;
}
int L = 0；
        int R = arr.length - 1;
        int M = 0;
while (L <= R) {
M = (L + R) / 2;
if (arr[M] == num) {
return true;
} else if (arr[M] > num) {
R = M - 1;
} else {
L = M + 1;
}
}
return false;
}

C语言实现

int exist(int arr[], int length, int num) {
    if (arr == NULL || length == 0) {
return 0;
}
int L = 0;
int R = length - 1;
    int M = 0;
while (L <= R) {
M = (L + R) / 2;
if (arr[M] == num) {
return 1;
}
else if (arr[M] < num) {
L = M + 1;
}
else {
R = M - 1;
}
}
return 0;
}

在有序数组中找>=num的最左位置

Java实现

public static int findLeftIndex(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int M = 0;
        int Index = -1;
        while (L <= R) {
            M = (L + R) / 2;  
            // 数组长度很长的时候有溢出风险
            // M = L + (R - L) / 2;
            // M = L + ((R - L) >> 1);
            if (arr[M] >= num) {
                Index = M;
                R = M - 1;
            } else {
                L = M + 1;
            }
        }
        return Index;
    }

C语言实现

int findLeftIndex(int arr[], int length, int num) {
int R = length - 1;
int L = 0;
int M = 0;
int Index = -1;
while (L <= R) {
        M = (R + L) / 2;
if (arr[M] >= num) {
Index = M;
R = M - 1;
}
else {
L = M + 1;
}
}
return Index;
}

在有序数组中找<=num的最右位置

Java实现

public static int findRightIndex(int[] arr, int num) {
int L = 0;
    int R = arr.length - 1;
    int M = 0;
int Index = -1;
while (L <= R) {
M = (L + R) / 2; 
if (arr[M] <= num) {
Index = M;
L = M + 1;
} else {
R = M - 1;
}
}
return Index;
}

C语言实现

int findRightIndex(int arr[], int length, int num) {
int R = length - 1;
int L = 0;
int M = 0;
int Index = -1;
while (L <= R) {
        M = (R + L) / 2;
if (arr[M] <= num) {
Index = M;
L = M + 1;
} else {
R = M - 1;
}
}
return Index;
}

原文地址：https://blog.csdn.net/m0_74209563/article/details/137645373

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！