/
githubmirror
/
hello-algo
Обзор
Документация
Войти
/
githubmirror
/
hello-algo
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
main
codes/javascript/chapter_searching/binary_search_edge.js
45 строк
1 KB
gaofer
Add code in javascript and typescript. (#690)
30 авг 2023, 00:21
Не верифицирован
30 авг 2023, 00:21
1b94b77
Код
Авторство
О чём код?
/** * File: binary_search_edge.js * Created Time: 2023-08-22 * Author: Gaofer Chou (gaofer-chou@qq.com) */ const { binarySearchInsertion } = require('./binary_search_insertion.js'); /* 二分查找最左一个 target */ function binarySearchLeftEdge(nums, target) { // 等价于查找 target 的插入点 const i = binarySearchInsertion(nums, target); // 未找到 target ，返回 -1 if (i === nums.length || nums[i] !== target) { return -1; } // 找到 target ，返回索引 i return i; } /* 二分查找最右一个 target */ function binarySearchRightEdge(nums, target) { // 转化为查找最左一个 target + 1 const i = binarySearchInsertion(nums, target + 1); // j 指向最右一个 target ，i 指向首个大于 target 的元素 const j = i - 1; // 未找到 target ，返回 -1 if (j === -1 || nums[j] !== target) { return -1; } // 找到 target ，返回索引 j return j; } /* Driver Code */ // 包含重复元素的数组 const nums = [1, 3, 6, 6, 6, 6, 6, 10, 12, 15]; console.log('\n数组 nums = ' + nums); // 二分查找左边界和右边界 for (const target of [6, 7]) { let index = binarySearchLeftEdge(nums, target); console.log('最左一个元素 ' + target + ' 的索引为 ' + index); index = binarySearchRightEdge(nums, target); console.log('最右一个元素 ' + target + ' 的索引为 ' + index); }