英文:
Search Insert Position Good Approach
问题
以下是翻译好的内容：
我在LeetCode上做了这个问题，并用Java创建了以下解决方案，并且成功地提交了它。
class Solution {
public int searchInsert(int[] nums, int val) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
if (nums[i] > val) {
return i;
}
}
if (nums[i] == val)
return i;
if (i == nums.length - 1 && nums[i] != val)
return i + 1;
}
return 0;
}
}
当我在Google上检查解决方案时，我找到了一个二分搜索的解决方案，如下所示：
class Test {
// 简单的二分搜索算法
static int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
}
我想问一下，我的方法是否比下面的二分搜索方法差？
英文:
I was doing this problem on leetcode and have created this solution for it in java and it was submitted successfully.
class Solution {
public int searchInsert(int[] nums, int val) {
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
if(nums[i]>val){
return i;
}
}
if(nums[i]==val)
return i;
if(i==nums.length-1 && nums[i]!=val)
return i+1;
}
return 0;
}
}
And when I checked it solution over the google I found a binary search solution which is this
class Test
{
// Simple binary search algorithm
static int binarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch`enter code here`(arr, mid+1, r, x);
}
return -1;
}
I want to ask that, Is my approach is poor than the below binary search approach?
答案1
得分: 1
二分查找是寻找插入点的更好解决方案。
你的解决方案将在 O(n) 时间内找到插入索引，而二分查找则在 O(log(n)) 时间内找到。
背景：这种类型的算法的时间复杂度是通过算法需要执行的比较次数来衡量的。
复杂度的差异在于你的解决方案在每次循环迭代中将搜索空间的宽度减少1 => 线性复杂度。
另一方面，二分查找将在每次递归调用时将搜索空间减半 => 对数复杂度。
英文:
The binary search is the better solution to find the insertion point.
Your solution will find the insertion index in O(n) and the binary search in O(log(n)).
For context: The time complexity for this kind of algorithem is measured at the number of comparisons the algorithem has to perform.
The difference in complexity comes is because your solution will decrease the width of the search space by 1 in each loop iteration => linear complexity.
On the other hand the binary search will cut the search space in half with each recursive call => logarithmic complexity.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论