二分法简单题

这篇具有很好参考价值的文章主要介绍了二分法简单题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二分法

222. 完全二叉树的节点个数

/*
 * 完全二叉树编号从1开始
 * 如果第k个节点位于第h层,则k的二进制表示包含h+1位,
 * 其中最高位是1,其余各位从高到低表示从根节点到第k个节点的路径,
 * 0表示移动到左子节点,1表示移动到右子节点。
 * 通过位运算得到第k个节点对应的路径,判断该路径对应的节点是否存在,即可判断第k个节点是否存在。
 */
bool exist(struct TreeNode *root, int height, int k) {
    // 树高height(从1开始),从根到叶节点需要往下走height-1次
    int count = height - 1;

    while (count-- > 0) {
        if (root == NULL) break;
        // 从第二位开始,根据每一位判断往左往右
        int bit = ((k >> count) & 1);
        if (bit == 0) {
            root = root->left;
        } else {
            root = root->right;
        }
    }

    // 返回是否存在
    return root != NULL;
}

int binarySearch(struct TreeNode *root, int height, int left, int right) {
    int mid;
    // 找最后一个节点的编号
    while (left <= right) {
        mid = (right - left) / 2 + left;
        if (exist(root, height, mid)) {
            // 若这个编号为mid的节点存在,往右找
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return right;
}

// 完全二叉树的节点个数
int countNodes(struct TreeNode *root) {
    if (root == NULL) return 0;
    struct TreeNode *node = root;
    int height = 0;
    while (node != NULL) {
        height++;
        node = node->left;
    }

    // 最下层,最左边的节点编号
    int left = (1 << (height - 1));
    // 最下层,最右边的节点编号
    int right = (1 << height) - 1;
    return binarySearch(root, height, left, right);
}

2089. 找出数组排序后的目标下标

int cmp(const void *a, const void *b) {
    return (*(int *) a - *(int *) b);
}

// 找左边界
int findLeft(int *nums, int left, int right, int target) {
    int mid;
    while (left <= right) {
        mid = (right - left) / 2 + left;
        if (nums[mid] >= target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

// 找右边界
int findRight(int *nums, int left, int right, int target) {
    int mid;
    while (left <= right) {
        mid = (right - left) / 2 + left;
        if (nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return right;
}

// 排完序后找左右边界
int *targetIndices(int *nums, int numsSize, int target, int *returnSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int left = findLeft(nums, 0, numsSize - 1, target);
    int right = findRight(nums, 0, numsSize - 1, target);
    int count = right - left + 1;

    *returnSize = 0;
    if (count <= 0)return NULL;
    int *res = (int *) malloc(sizeof(int) * count);
    for (int i = 0; i < count; ++i) {
        res[(*returnSize)++] = left + i;
    }
    return res;
}

2529. 正整数和负整数的最大计数

int countPos(int *array, int start, int end) {
    // 全是非正数
    if (array[end] <= 0) return 0;
    // 左右边界
    int i;
    int j = end;

    int left = start, right = end;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] > 0)
            right = mid - 1;
        else
            left = mid + 1;
    }
    i = left;
    return j - i + 1;
}

int countNeg(int *array, int start, int end) {
    // 全是非负数
    if (array[start] >= 0) return 0;
    // 左右边界
    int i = start;
    int j;

    int left = start, right = end;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] >= 0)
            right = mid - 1;
        else
            left = mid + 1;
    }
    j = right;
    return j - i + 1;
}

int maximumCount(int *nums, int numsSize) {
    int i = countPos(nums, 0, numsSize - 1);
    int j = countNeg(nums, 0, numsSize - 1);
    return i > j ? i : j;
}

1351. 统计有序矩阵中的负数

// 在非递增序列中找-1插入的左边界
int findPosition(int *array, int left, int right) {
    int mid;
    int target = -1;
    while (left <= right) {
        mid = (right - left) / 2 + left;
        if (array[mid] <= target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

// 一行行统计,没有利用到列也是非递增的条件
int countNegatives(int **grid, int gridSize, int *gridColSize) {
    int res = 0;
    for (int i = 0; i < gridSize; ++i) {
        res += gridColSize[i] - findPosition(grid[i], 0, gridColSize[i] - 1);
    }
    return res;
}
// 在非递增序列中找-1插入的左边界
int findPosition(int *array, int left, int right) {
    int mid;
    int target = -1;
    while (left <= right) {
        mid = (right - left) / 2 + left;
        if (array[mid] <= target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

// 每一行从前往后第一个负数的位置是不断递减的
// 右边界也就是-1插入的位置,也就是负数应该出现的位置,下标不断减小。没必要每次都以gridSize作为二分法右边界
int countNegatives(int **grid, int gridSize, int *gridColSize) {
    int res = 0;

    int tempPos = gridColSize[0];
    int temp;
    // 处理每行
    for (int i = 0; i < gridSize; ++i) {
        // 下标从0到第一个负数出现的位置
        temp = findPosition(grid[i], 0, tempPos - 1);
        res += gridColSize[i] - temp;
        // 更新第一个负数的下标
        tempPos = temp;
    }
    return res;
}

2389. 和有限的最长子序列

int cmp(const void *a, const void *b) {
    return (*(int *) a - *(int *) b);
}

// 找右边界
int binarySearch(int *array, int left, int right, int target) {
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] <= target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right;
}

int *answerQueries(int *nums, int numsSize, int *queries, int queriesSize, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * queriesSize);
    *returnSize = queriesSize;
    qsort(nums, numsSize, sizeof(int), cmp);

    // 保存前缀和
    int sum[numsSize];
    sum[0] = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        sum[i] = sum[i - 1] + nums[i];
    }

    // 在前缀和数组里二分查找
    for (int i = 0; i < queriesSize; ++i) {
        res[i] = binarySearch(sum, 0, numsSize - 1, queries[i]) + 1;
    }
    return res;
}

LCR 069. 山脉数组的峰顶索引

// todo
int peakIndexInMountainArray(int *arr, int arrSize) {
    int left = 0;
    int right = arrSize - 1;
    int mid;
    while (left < right) {
        mid = left + (right - left) / 2;
        if (arr[mid] < arr[mid + 1]) {
            // left左边全都小于arr[left], arr[left]=arr[mid + 1]最大
            left = mid + 1;
        } else if (arr[mid] > arr[mid + 1]) {
            // right右边全都小于arr[right],arr[right]=arr[mid]最大
            right = mid;
        }
    }
    return left;
}

1337. 矩阵中战斗力最弱的 K 行

// todo

LCR 179. 查找总价格为目标值的两个商品

// 双指针
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 2);
    *returnSize = 0;

    int left = 0, right = numbersSize - 1;

    while (left < right) {
        if (numbers[left] == target - numbers[right]) {
            res[0] = numbers[left];
            res[1] = numbers[right];
            *returnSize = 2;
            return res;
        } else if (numbers[left] > target - numbers[right]) {
            right--;
        } else {
            left++;
        }
    }
    return res;
}
// 散列
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 2);
    *returnSize = 0;

    int *hashMap = (int *) calloc(2000001, sizeof(int));
    for (int i = 0; i < numbersSize; ++i) {
        if ((target - numbers[i]) > 0 && hashMap[target - numbers[i]] == 1) {
            res[0] = numbers[i];
            res[1] = target - numbers[i];
            *returnSize = 2;
            return res;
        }
        hashMap[numbers[i]] = 1;
    }
    return res;
}

面试题 08.03. 魔术索引

// todo
// 二分+递归
int binarySearch(int *array, int left, int right) {
    if (left > right) return -1;
    int mid = ((right - left) >> 1) + left;
    // 左区间能找到就返回左区间
    int leftAns = binarySearch(array, left, mid - 1);
    if (leftAns != -1) return leftAns;
    // 左区间找不到就检查当前节点
    if (array[mid] == mid) return mid;
    // 当前节点也不满足就检查右区间
    return binarySearch(array, mid + 1, right);
}

int findMagicIndex(int *nums, int numsSize) {
    return binarySearch(nums, 0, numsSize - 1);
}

LCR 006. 两数之和 II - 输入有序数组

// 双指针
// 假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 2);
    *returnSize = 0;

    int left = 0, right = numbersSize - 1;

    while (left < right) {
        if (numbers[left] == target - numbers[right]) {
            res[0] = left;
            res[1] = right;
            *returnSize = 2;
            return res;
        } else if (numbers[left] > target - numbers[right]) {
            right--;
        } else {
            left++;
        }
    }
    return res;
}
int binarySearch(int *array, int left, int right, int target) {
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

// 假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次
// 在当前节点的右边二分查找
int *twoSum(int *numbers, int numbersSize, int target, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 2);
    *returnSize = 0;

    for (int i = 0; i < numbersSize; ++i) {
        int k = binarySearch(numbers, i + 1, numbersSize - 1, target - numbers[i]);
        if (k != -1) {
            res[0] = i;
            res[1] = k;
            *returnSize = 2;
            return res;
        }
    }
    return res;
}

1385. 两个数组间的距离值


int cmp(const void *a, const void *b) {
    return (*(int *) a - *(int *) b);
}

// 大于等于(找应该插入的位置,左边界)
int binarySearch1(int *array, int size, int target) {
    int left = 0;
    int right = size - 1;
    int mid;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (target > array[mid])
            left = mid + 1;     // left更新之后,left左边必然都小于target
        else if (target <= array[mid])
            right = mid - 1;    // right更新之后,right右边必然都大于等于target
    }
    // 循环结束时left = right + 1
    return left;
}

// 小于等于(右边界)
int binarySearch2(int *array, int size, int target) {
    int left = 0;
    int right = size - 1;
    int mid;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (target >= array[mid])  // 即使等于left也右移,这样小于等于的就都在left左边了,循环结束时,right就在left-1的位置
            left = mid + 1;     // left更新之后,left左边必然都小于等于target
        else if (target < array[mid])
            right = mid - 1;    // right更新之后,right右边必然都大于target
    }
    return right;
}

// 求arr1中与arr2所有元素之差绝对值大于d的元素个数
int findTheDistanceValue(int *arr1, int arr1Size, int *arr2, int arr2Size, int d) {
    qsort(arr2, arr2Size, sizeof(int), cmp);
    int sum = 0;
    for (int i = 0; i < arr1Size; ++i) {
        int right = binarySearch1(arr2, arr2Size, arr1[i]);
        int left = binarySearch2(arr2, arr2Size, arr1[i]);
        printf("%d %d\n", left, right);
        if ((left < 0 || abs(arr2[left] - arr1[i]) > d)
            && (right >= arr2Size || abs(arr2[right] - arr1[i]) > d)) {

            sum++;

        }
    }
    return sum;
}

888. 公平的糖果交换

int cmp(const void *a, const void *b) {
    return *(int *) a - *(int *) b;
}

int binarySearch(int *array, int size, int target) {
    int left = 0;
    int right = size - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (target == array[mid])
            return mid;
        else if (target < array[mid])
            right = mid - 1;
        else
            left = mid + 1;
    }
    return -1;
}

int *fairCandySwap(int *aliceSizes, int aliceSizesSize, int *bobSizes, int bobSizesSize, int *returnSize) {
    int *res = (int *) malloc(sizeof(int) * 2);
    *returnSize = 2;
    
    // 先把bobSizes排序,再根据aliceSizes[i]在bobSizes中二分查找
    qsort(bobSizes, bobSizesSize, sizeof(int), cmp);
    int sum1 = 0, sum2 = 0;
    for (int i = 0; i < aliceSizesSize; ++i) sum1 += aliceSizes[i];
    for (int i = 0; i < bobSizesSize; ++i) sum2 += bobSizes[i];
    // sum1给出x,sum2给出y
    // sum1-x+y = sum2-y+x
    // gap = sum1-sum2 = 2*(x-y)
    // y = x - gap/2
    int gap = sum1 - sum2;

    for (int i = 0; i < aliceSizesSize; ++i) {
        int t = binarySearch(bobSizes, bobSizesSize, aliceSizes[i] - gap / 2);
        if (t != -1) {
            res[0] = aliceSizes[i];
            res[1] = bobSizes[t];
            return res;
        }
    }
    return res;
}

1608. 特殊数组的特征值

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

// 左边界
int binarySearch(int *array, int size, int target) {
    int left = 0;
    int right = size - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] >= target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

int specialArray(int *nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), cmp);
    for (int i = 0; i <= nums[numsSize - 1]; ++i) {
        int index = binarySearch(nums, numsSize, i);
        if (numsSize - index == i)
            return i;
    }
    return -1;
}

350. 两个数组的交集 II

// 散列
int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
    int min = nums1Size > nums2Size ? nums2Size : nums1Size;
    int *res = (int *) malloc(sizeof(int) * min);
    *returnSize = 0;
    int *hashMap = (int *) calloc(1001, sizeof(int));

    // 统计出现次数
    for (int i = 0; i < nums1Size; ++i) hashMap[nums1[i]]++;
    for (int i = 0; i < nums2Size; ++i) {
        if (hashMap[nums2[i]] > 0) {
            // 表中减一
            hashMap[nums2[i]]--;
            res[(*returnSize)++] = nums2[i];
        }
    }
    return res;
}
// 左边界
int binarySearch(int *array, int left, int right, int target) {
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] >= target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

int cmp(const void *a, const void *b) {
    return *(int *) a - *(int *) b;
}

// 排序后双指针,第二个指针用二分法定位
int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize) {
    int min = nums1Size > nums2Size ? nums2Size : nums1Size;
    int *res = (int *) malloc(sizeof(int) * min);
    *returnSize = 0;

    // 排序
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);

    int j = 0;
    for (int i = 0; i < nums1Size && j < nums2Size; ++i) {
        int k = binarySearch(nums2, j, nums2Size - 1, nums1[i]);
        if (k >= 0 && k < nums2Size && nums1[i] == nums2[k]) {
            res[(*returnSize)++] = nums1[i];
            // 数组2的j指针同时后移
            j = k + 1;
        }
    }
    return res;
}

面试题 10.05. 稀疏数组搜索

int binarySearch(char **words, int left, int right, char *s) {
    int mid;
    while (left <= right) {
        // 跳过左右的空字符串
        while (left <= right && strcmp(words[left], "") == 0) left++;
        while (left <= right && strcmp(words[right], "") == 0) right--;

        mid = ((right - left) >> 1) + left;
        // 中间的是空字符串,就在两侧找
        if (strcmp(words[mid], "") == 0) {
            // 找左边
            int leftAns = binarySearch(words, left, mid - 1, s);
            if (leftAns != -1) return leftAns;
            // 找右边
            return binarySearch(words, mid + 1, right, s);
        }

        // 中间不是空字符串
        int k = strcmp(words[mid], s);
        if (k == 0) {
            return mid;
        } else if (k > 0) {
            right = mid - 1;
        } else if (k < 0) {
            left = mid + 1;
        }
    }

    return -1;
}

// 二分+递归
int findString(char **words, int wordsSize, char *s) {
    return binarySearch(words, 0, wordsSize - 1, s);
}
int findString(char **words, int wordsSize, char *s) {
    int left = 0, right = wordsSize - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        int beforeMid = mid;

        // 无法二分时,线性探测
        while (mid <= right && strcmp(words[mid], "") == 0) {
            mid++;
        }

        if (mid <= right) {
            // 没有越界,words[mid]一定不是空字符串
            if (strcmp(words[mid], s) == 0) {
                return mid;
            } else if (strcmp(words[mid], s) > 0) {
                right = beforeMid - 1;
            } else {
                left = mid + 1;
            }
        } else {
            right = beforeMid - 1;
        }
    }
    return -1;
}

1539. 第 k 个缺失的正整数


int findKthPositive(int *arr, int arrSize, int k) {
    int left = 0, right = arrSize - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        // 到arr[mid]为止,包括arr[mid],缺失的正整数个数
        int lossCount = arr[mid] - mid - 1;
        // 找左边界
        if (lossCount >= k) {
            // 代码a,执行这条代码,right右面的必然都满足lossCount >= k
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 循环结束一定是left=right+1
    // right是刚好lossCount严格小于k的位置,下个位置right+1是lossCount大于等于k的位置(代码a决定的)
    if (right >= 0) {
        
        // index        = [0,1,2,3,4]
        // array        = [2,3,4,7,11]
        // lossCount    = [1,1,1,3,6]
        // right = 3, arr[right] = 7, lossCount[right] = 3, lossCount[right+1] = 6
        // lossCount[right] < k < lossCount[right+1],丢失的数一定就在arr[right]到arr[right+1]之间

        // 到arr[right]为止,包括arr[right],缺失的正整数个数为lossCount,从arr[right]往后数(k-lossCount)个数就是答案
        return k - (arr[right] - (right) - 1) + arr[right];
    }
    return k;
}

LCR 172. 统计目标成绩的出现次数

// 左边界
int binarySearch1(int *array, int size, int target) {
    int left = 0, right = size - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] >= target)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

// 右边界
int binarySearch2(int *array, int size, int target) {
    int left = 0, right = size - 1;
    int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        if (array[mid] <= target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right;
}

int countTarget(int *scores, int scoresSize, int target) {
    int left = binarySearch1(scores, scoresSize, target);
    int right = binarySearch2(scores, scoresSize, target);
    if(left >= scoresSize || scores[left] != target) return 0;
    return right - left + 1;
}

154. 寻找旋转排序数组中的最小值 II

// todo
// 含重复元素的增序数组,循环右移后找最小元素
int findMin(int *nums, int numsSize) {
    int left = 0;
    int right = numsSize - 1;
    int mid;
    // 规律:最小值下标x,[0,x)值都大于等于末尾元素,[x,array.length-1]都小于等于末尾元素
    while (left < right) {
        mid = left + (right - left) / 2;
        // 和末尾元素比较
        if (nums[mid] > nums[right]) {
            // [left, mid]都大于numbers[right],都排除
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            // numbers[mid]是[mid,right]上最小的,忽略(mid,right]上的
            right = mid;
        } else {
            // 忽略末尾,新的末尾numbers[right-1]也符合规律
            right--;
        }
    }
    return nums[left];
}

441. 排列硬币

// 右边界
int arrangeCoins(int n) {
    int left = 1, right = n;
    long int mid;
    // k行全满,共(1+k)*k/2个元素
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        long int sum = (1 + mid) * mid >> 1;
        if (sum <= n)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right;
}

367. 有效的完全平方数

// 小于等于(右边界
bool isPerfectSquare(int num) {
    int left = 0;
    int right = num;
    long int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        long int temp = mid * mid;
        if (temp <= num)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right * right == num;
}

LCR 072. x 的平方根

// 小于等于(右边界
int mySqrt(int x) {
    int left = 0;
    int right = x;
    long int mid;
    while (left <= right) {
        mid = ((right - left) >> 1) + left;
        long int temp = mid * mid;
        if (temp <= x)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return right;
}

文章来源地址https://www.toymoban.com/news/detail-819655.html

到了这里,关于二分法简单题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【二分查找】一文带你掌握二分法 (附万能模板)

    一、简介 哪怕没有学过编程的同学,也许不知道二分法这个名字,但也一定接触过它的核心思想。不了解的同学也没关系,我用一句话就能概括出它的精髓: 将一个区间一分为二,每次都舍弃其中的一部分。 二分法能够极大地降低我们在解决问题时的时间复杂度。假如你要

    2024年01月19日
    浏览(58)
  • 【剑指Offer】二分法例题

    链表是数据结构中重要的一个章节,他的重要性也不言而喻,在未来不管是笔试还是面试都会遇到这类的题目,所以接下来我就会把一些链表的常考的题目全部整理出来供大家学习指正。 题目链接 描述: 给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包

    2023年04月13日
    浏览(45)
  • 非线性方程二分法

    优点:算法直观、简单、总能保证收敛;局限:收敛速度慢、一般不单独用它求根,仅为了获取根的粗略近似 设 f ( x ) f(x) f ( x ) 在 [ a , b ] [a,b] [ a , b ] 上连续、严格单调、满足条件 f ( a ) f ( b ) 0 f(a)f(b)0 f ( a ) f ( b ) 0 则在区间 [ a , b ] [a,b] [ a , b ] 内必有一根 x ∗ x^* x ∗ 。通

    2024年02月04日
    浏览(48)
  • 牛顿法、割线法、二分法

    牛顿法求解非线性方程组 割线法求解非线性方程组 二分法求解根号3  另外,今天上机课写程序时,发现不同的起始点可以收敛到不同的零点。也许这是一个新的值得研究的地方。 看来,计算数学也是这样,光听理论无法实现大的突破,也没法产生好的想法,必须在实践应用

    2024年02月05日
    浏览(51)
  • 1241:二分法求函数的零点

    【题目描述】 有函数:f(x)=x5−15x4+85x3−225x2+274x−121 已知f(1.5)0,f(2.4)0 且方程f(x)=0在区间[1.5,2.41.5,2.4] 有且只有一个根,请用二分法求出该根。 【输入】 (无) 【输出】 该方程在区间[1.5,2.41.5,2.4]中的根。要求四舍五入到小数点后66位。 【输入样例】 【输出样例】 【AC代码】

    2024年01月25日
    浏览(36)
  • Leetcode刷题笔记——二分法

    二分法是搜索算法中极其典型的方法,其要求输入序列有序并可随机访问。算法思想为 输入:有序数组nums,目的数值target 要求输出:如果target存在在数组中,则输出其index,否则输出-1 将原数组通过[left,right]两个索引划分范围,初值left=0,right=数组的最后一个元素 当left = r

    2024年02月10日
    浏览(42)
  • 06-C++ 基本算法 - 二分法

    在这个笔记中,我们将介绍二分法这种基本的算法思想,以及它在 C++ 中的应用。我们将从一个小游戏猜数字开始,通过这个案例来引出二分法的概念。然后我们将详细讲解什么是二分法以及它的套路和应用。最后,我们还会介绍 C++ STL 中的二分查找函数。让我们一起来探索

    2024年02月16日
    浏览(45)
  • 算法:二分法---寻找H指数

    1、题目: 给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数 。 根据维基百科上 h 指数的定义: h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每篇论文 至少 被引用

    2024年02月08日
    浏览(44)
  • 33. 搜索旋转排序数组(二分法)

    题目要求必须设计一个时间复杂度为  O(log n)  的算法解决此问题,所以我们可以采用二分法。 Step1. 先把 nums[0] 作为目标值,通过二分法找到旋转点索引; Step2. 如果旋转点索引为0,则数组本身就是升序的,否则思想上可以将数组一分为二,看做两个升序数组。 Step3. 判断

    2024年02月05日
    浏览(38)
  • 二分法的原理及其应用举例

    首先,什么是二分法:         最简单的例子就是类似于二分查找的用法来实现快速查找有序区间内的给定的目标值是否存在,当然,这也可以应用在别的问题中,二分查找是一个时间效率极高的算法,尤其是面对大量的数据时,其查找效率是极高,时间复杂度是log(n)。如果

    2024年02月06日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包