[LeetCode] Search Insert Position
LeetCode search INSERT position
2023-09-11 14:17:25 时间
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.[1,3,5,6]
, 5 → 2[1,3,5,6]
, 2 → 1[1,3,5,6]
, 7 → 4[1,3,5,6]
, 0 → 0
方法一:线性搜索
class Solution { public: int searchInsert(int A[], int n, int target) { int i; for( i = 0; i < n; i++) { if(A[i] >= target) return i; } return i; } };
方法二:此题的意图应该不是线性搜索,应该是二分
注意两点,第一,当A[mid] > target时,mid本身有可能就是答案,
第二,当left==right时,由于 target有可能大于A[right],这时,要返回right+1,而不是right
class Solution { public: #if 0 int searchInsert(int A[], int n, int target) { int i; for( i = 0; i < n; i++) { if(A[i] >= target) return i; } return i; } #endif int searchInsert(int A[], int n, int target) { return binarySearch(A, 0, n-1, target); } int binarySearch(int A[], int left, int right, int target) { if(left == right) { if(A[left] >= target) return left; else return right + 1; } int mid = (left + right)/2; if(A[mid] == target) return mid; if(A[mid] > target)//mid may be the answer return binarySearch(A, left, mid , target); if(A[mid] < target) return binarySearch(A, mid+1, right, target); } };
相关文章
- Leetcode: Ransom Note
- Leetcode: Best Meeting Point
- Leetcode: Closest Binary Search Tree Value II
- Leetcode: Lowest Common Ancestor of a Binary Search Tree
- Leetcode: Binary Tree Postorder Transversal
- Leetcode: Search Insert Position
- Leetcode Validate Binary Search Tree
- [Leetcode] Convert Sorted List to Binary Search Tree
- [LeetCode] Unique Binary Search Trees
- [LeetCode] Permutations II
- 【leetcode】日积月累,每日一题--11 盛最多水的容器(DayDayUp 10)
- 【LeetCode】211. Add and Search Word - Data structure design
- 【LeetCode】206. Reverse Linked List (2 solutions)
- Leetcode:search_insert_position
- [LeetCode]Search Insert Position
- [LeetCode] 1305. All Elements in Two Binary Search Trees 两棵二叉搜索树中的所有元素
- [LeetCode] 834. Sum of Distances in Tree 树中距离之和
- [LeetCode] 483. Smallest Good Base 最小的好基数
- [LeetCode] Find Mode in Binary Search Tree 找二分搜索数的众数
- [LeetCode] 362. Design Hit Counter 设计点击计数器
- [LeetCode] Rank Scores 分数排行
- [LeetCode] 312. Burst Balloons 打气球游戏
- [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最小共同父节点
- [LeetCode] Add and Search Word - Data structure design 添加和查找单词-数据结构设计
- [LeetCode] Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树
- Leetcode——20. Valid Parentheses
- leetcode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先(简单)
- leetcode 669. Trim a Binary Search Tree 修剪二叉搜索树 (简单)
- leetcode算法231.2 的幂