毕业设计做啥网站好,廊坊网站公司,在线手机网站制作,有哪些企业官网做得比较好二分查找 1. 搜索插入位置2. 搜素二维矩阵3. 在排序数组中查找第一个和最后一个元素位置 1. 搜索插入位置
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;并返回其索引。如果目标值不存在于数组中#xff0c;返回它将会被按顺序插入的位置。
// 题… 二分查找 1. 搜索插入位置2. 搜素二维矩阵3. 在排序数组中查找第一个和最后一个元素位置 1. 搜索插入位置
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
// 题解
int searchInsert(vectorint nums, int target) {if (nums.empty()) {return 0;}int left 0;int right nums.size() - 1;while (left right) {int mid (left right) 1;if (nums[mid] target) {left mid 1;} else {right mid;}}return right ;
}2. 搜素二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。
// 题解按照行和最后一列遍历对row和col加减
bool searchMatrix(vectorvectorint matrix, int target) {if (matrix.empty()) return false;int rows matrix.size();if (matrix[0].empty()) return false;int cols matrix[0].size();int row 0;int col cols - 1;while (col cols col 0 row rows row 0) {if (matrix[row][col] target) row;else if (matrix[row][col] target) col--;else return true;}return false;
}3. 在排序数组中查找第一个和最后一个元素位置
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 输入nums [5,7,7,8,8,10], target 8 输出[3,4]
// 题解两次二分法找到左和右
vectorint searchRange(vectorint nums, int target) {int left 0;int right nums.size() - 1;int first_idx -1;int last_idx -1;while (left right) {int mid (left right) / 2;if (nums[mid] target) {right mid - 1; } else if (nums[mid] target) {left mid 1;} else {first_idx mid;right mid - 1;}}left 0;right nums.size() - 1;while (left right) {int mid (left right) / 2;if (nums[mid] target) {right mid - 1;} else if (nums[mid] target) {left mid 1;} else {last_idx mid;left mid 1;}}return {first_idx, last_idx};
}
