Lintcode: First Position of Target (Binary Search)
of search Binary Target First position lintcode
2023-09-11 14:14:08 时间
Binary search is a famous question in algorithm. 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. Example If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2. Challenge If the count of numbers is bigger than MAXINT, can your code work properly?
跟Leetcode里search for a range挺像的,就是找到一个target之后,还要继续找它的左边沿。最后l指针超过r指针之后, l 指针会停在左边沿上
1 class Solution { 2 /** 3 * @param nums: The integer array. 4 * @param target: Target to find. 5 * @return: The first position of target. Position starts from 0. 6 */ 7 public int binarySearch(int[] nums, int target) { 8 int l = 0, r = nums.length - 1; 9 int m = 0; 10 while (l <= r) { 11 m = (l + r) / 2; 12 if (nums[m] == target) break; 13 else if (nums[m] > target) r = m - 1; 14 else l = m + 1; 15 } 16 if (nums[m] != target) return -1; 17 l = 0; 18 r = m; 19 while (l <= r) { 20 m = (l + r) / 2; 21 if (nums[m] == target) { 22 r = m - 1; 23 } 24 else l = m + 1; 25 } 26 return l; 27 } 28 }
相关文章
- HTC 328T 提示手机存储不足 out of space怎么办
- RMAN-03002, RMAN-06059, ORA-19625 and ORA-27037 When Running RMAN Backup of Archivelogs
- Vue循环中v-for和of,in
- the terminal server has exceeded the maximum number of allowed connections
- Json解析异常处理方式(JSONException: Value of type java.lang.String cannot be converted to JSONObject)
- [Git] Change the commit message of my last commit
- [LeetCode] Bitwise AND of Numbers Range
- The .NET of Tomorrow
- SAP UI5 ConnectionManager - drives initialization of odata model
- Enterprise search - Build Search dropdown list - cache issue
- Technical implementation of loyalty program search
- No cached version of ******available for offline mode.
- [LeetCode]235.Lowest Common Ancestor of a Binary Search Tree
- PLoP(Pattern Languages of Programs,程序设计的模式语言)
- 执行git命令报错:fatal: not a git repository (or any of the parent directories): .git
- WSL2编译android12之You are building on a machine with 15GB of RAM解决
- 嵌入式linux开发,rtc时钟探测报错:rtc-ds1307: probe of 1-0068 failed with error -5