[Algorithm] Count occurrences of a number in a sorted array with duplicates using Binary Search
in of number with Using Array search Binary
2023-09-14 08:59:14 时间
Let's say we are going to find out number of occurrences of a number in a sorted array using binary search in O(log n) time.
For example the given array is:
[1,1,3,5,5,5,5,5,9,11],
the number 5 appears 5 times;
the number 3 appears 1 time;
2 appears 0 times.
The idea:
we can use binary search twice, first time is to find first index of target number in the array; second is to find last index of given number in the array.
function count_numbers(ary, target) { function helper(ary, target, isFirst) { let start = 0; let end = ary.length - 1; let result = -1; while (start <= end) { let mid = Math.floor((start + end) / 2); if (ary[mid] === target) { result = mid; isFirst ? (end = mid - 1) : (start = mid + 1); } else { ary[mid] > target ? (end = mid - 1) : (start = mid + 1); } } return result; } const first = helper(ary, target, true); const last = helper(ary, target, false); if (first === -1 || last === -1) { return 0; } return last - first + 1; } console.log(count_numbers([1, 1, 3, 3, 5, 5, 5, 5, 5, 8, 11], 5)); // 5
相关文章
- ORA-01604: illegal number range in clause “string” of string ORACLE 报错 故障修复 远程处理
- ORA-19295: XQST0060: It is a static error if the name of a function in a function declaration is not in a namespace (expanded QName has a null namespace URI) ORACLE 报错 故障修复 远程处理
- ORA-22140: given size [string] must be in the range of 0 to [string] ORACLE 报错 故障修复 远程处理
- ORA-25004: WHEN clause is not allowed in INSTEAD OF triggers ORACLE 报错 故障修复 远程处理
- ORA-25286: Invalid number of elements in the message properties array ORACLE 报错 故障修复 远程处理
- ORA-39914: Index string.string in tablespace string points to subpartition string of table string.string in tablespace string outside of transportable set. ORACLE 报错 故障修复 远程处理
- ORA-40118: insufficient number of target values in weights table ORACLE 报错 故障修复 远程处理
- ORA-41662: number of primitive events in the composite event exceeds maximum limit ORACLE 报错 故障修复 远程处理
- ORA-55318: column string in table string already contains data ORACLE 报错 故障修复 远程处理
- ORA-12521: TNS:listener does not currently know of instance requested in connect descriptor ORACLE 报错 故障修复 远程处理
- ORA-13053: maximum number of geometric elements in argument list exceeded ORACLE 报错 故障修复 远程处理
- ORA-13265: geometry identifier column string in table string is not of type NUMBER ORACLE 报错 故障修复 远程处理
- ORA-14152: invalid number of partitions specified in PARTITIONS clause ORACLE 报错 故障修复 远程处理
- ORA-14294: Number of partitions does not match number of subpartitions ORACLE 报错 故障修复 远程处理
- ORA-15269: group identification number not in range of [string,string] ORACLE 报错 故障修复 远程处理
- ORA-15411: Failure groups in disk group string have different number of disks. ORACLE 报错 故障修复 远程处理
- ORA-15485: number of volumes in diskgroup exceeds the maximum of string ORACLE 报错 故障修复 远程处理
- ORA-16503: cannot exceed the maximum number of databases in this configuration ORACLE 报错 故障修复 远程处理
- 查询MySQL中的IN字符串查询详解(mysql字符串in)
- Mysql | Understanding the Power of Diff Function in Database Management(mysqldiff)
- Exploring the Vast Capabilities of Linux in Camera Applications(linux摄像头应用)
- Exploring the Benefits of Using .deb Files in Linux Systems.(linux.deb文件)
- 限制解除Oracle中IN语句数量限制(oracle中in的数量)