Problem
For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
ExampleIf the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.
challengeIf the count of numbers is bigger than 2^32, can your code work properly?
Note</>复制代码
while (start + 1 < end)
+1 guaranteed that there always exists mid.
In the for loop, the else branch is actually when num[mid] >= target, why? Because this ensures that the mid pointer goes to the former ones if target is right in the middle.
</>复制代码
class Solution {
public int binarySearch(int[] nums, int target) {
//write your code here
if (nums == null || nums.length < 1) {
return -1;
}
int len = nums.length;
int start = 0, end = len - 1;
while (start + 1 < end) {
//for the challenge: avoid overflow
int mid = start + (end - start) / 2;
if (nums[mid] < target) {
start = mid;
}
else {
end = mid;
}
}
//after the while loop, only num[start] and num[end] left.
//so just discuss them
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
}
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65482.html
摘要:首先,建立二元结果数组,起点,终点。二分法求左边界当中点小于,移向中点,否则移向中点先判断起点,再判断终点是否等于,如果是,赋值给。 Problem Given a sorted array of n integers, find the starting and ending position of a given target value. If the target is not...
Problem For a given source string and a target string, you should output the first index(from 0) of target string in source string. If target does not exist in source, just return -1. Note 我终于找到了比较好的K...
摘要:建立动规数组,表示从起点处到达该点的可能性。循环结束后,数组对所有点作为终点的可能性都进行了赋值。和的不同在于找到最少的步数。此时的一定是满足条件的最小的,所以一定是最优解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...
Problem Xiao Ming is going to help companies buy fruit. Give a codeList, which is loaded with the fruit he bought. Give a shoppingCart, which is loaded with target fruit. We need to check if the order...
Problem Implement a trie with insert, search, and startsWith methods. Example insert(lintcode) search(code) // return false startsWith(lint) // return true startsWith(linterror) // return false insert...
阅读 678·2021-08-17 10:15
阅读 1796·2021-07-30 14:57
阅读 2010·2019-08-30 15:55
阅读 2855·2019-08-30 15:55
阅读 2741·2019-08-30 15:44
阅读 712·2019-08-30 14:13
阅读 2418·2019-08-30 13:55
阅读 2626·2019-08-26 13:56
极致性价比!云服务器续费无忧!
Tesla A100/A800、Tesla V100S等多种GPU云主机特惠2折起,不限台数,续费同价。
NVIDIA RTX 40系,高性价比推理显卡,满足AI应用场景需要。
乌兰察布+上海青浦,满足东推西训AI场景需要