1. 顺序查找算法总是查找数据集中匹配到的第一个元素。请重写该算法使之返回匹配到的 最后一个元素。
function seqSearchLast(arr, data) {var lastIndex = -1;for (var i = 0; i < arr.length; i++) {if (arr[i] == data) {lastIndex = i;}}return lastIndex;
}function dispArr(arr) { for (var i = 0; i < arr.length; ++i) { console.log(arr[i] + " "); if (i % 10 == 9) { console.log("\n"); } } if (i % 10 != 0) { console.log("\n"); }
} var nums = [];
for (var i = 0; i < 10; ++i) { nums[i] = Math.floor(Math.random() * 11);
}
dispArr(nums);
var readline = prompt("输入一个要查找的数字：");
var num = parseInt(readline);
var lastIndex = seqSearchLast(nums, num);
if (lastIndex !== -1) {console.log(num + " 最后出现在数组中的位置是：" + lastIndex);
} else {console.log(num + " 没有出现在这个数组中。");
}2. 对同一个数据集进行测试，比较顺序查找算法执行所花费的时间与同时使用插入排序算 法和二分查找算法花费的总时间。你得到的结果是什么？
function seqSearch(arr, data) { for (var i = 0; i < arr.length; ++i) { if (arr[i] == data) { return i; } } return -1;
}function findMin(arr) { var min = arr[0]; for (var i = 1; i < arr.length; ++i) { if (arr[i] < min) { min = arr[i]; } } return min;
}function findMax(arr) { var max = arr[0]; for (var i = 1; i < arr.length; ++i) { if (arr[i] > max) { max = arr[i]; } } return max;
}function swap(arr, index, index1) { temp = arr[index]; arr[index] = arr[index1];arr[index1] = temp;
}function seqSearch1(arr, data) { for (var i = 0; i < arr.length; ++i) { if (arr[i] == data && i > (arr.length * 0.2)) { swap(arr, i, 0); return true; } else if (arr[i] == data) {return true;}} return false;
}function insertionsort(arr) { var temp, inner; for (var outer = 1; outer <= arr.length-1; ++outer) { temp = arr[outer];inner = outer; while (inner > 0 && (arr[inner-1] >= temp)) { arr[inner] = arr[inner-1]; --inner; } arr[inner] = temp; }
} function binSearch(arr, data) { var upperBound = arr.length-1; var lowerBound = 0; while (lowerBound <= upperBound) { var mid = Math.floor((upperBound + lowerBound) / 2); if (arr[mid] < data) { lowerBound = mid + 1; } else if (arr[mid] > data) { upperBound = mid - 1; } else { return mid; } } return -1;
} function count(arr, data) { var count = 0; var position = binSearch(arr, data); if (position > -1) { ++count; for (var i = position-1; i > 0; --i) { if (arr[i] == data) { ++count; } else { break; } } for (var i = position+1; i < arr.length; ++i) { if (arr[i] == data) { ++count; } else { break; } } } return count;
}function generateRandomArray(size, maxVal) {let arr = [];for (let i = 0; i < size; ++i) {arr.push(Math.floor(Math.random() * maxVal));}return arr;
}
function testSequentialSearch(arr, data) {let startTime = performance.now();seqSearch(arr, data);let endTime = performance.now();return endTime - startTime;
}
function testInsertionSortAndBinarySearch(arr, data) {let startTime = performance.now();insertionsort(arr);let sortTime = performance.now() - startTime;startTime = performance.now();binSearch(arr, data);let searchTime = performance.now() - startTime;return sortTime + searchTime;
}
function main() {const size = 10000; const maxVal = 100000; const data = Math.floor(Math.random() * maxVal); let arr = generateRandomArray(size, maxVal);console.log("Sequential Search Time:", testSequentialSearch(arr.slice(), data), "ms");console.log("Insertion Sort + Binary Search Time:", testInsertionSortAndBinarySearch(arr.slice(), data), "ms");
}main();//Sequential Search Time: 0.4 ms
//Insertion Sort + Binary Search Time: 26.4ms3. 创建一个函数用来查找数据集中的次小元素。你能否归纳一下，如何实现查找第三小、 第四小，等等的搜索函数？在至少有 1000 个元素的数据集上测试你的函数。请同时在 数字和文本数据集上进行测试。
function seqSearch(arr, data) { for (var i = 0; i < arr.length; ++i) { if (arr[i] == data) { return i; } } return -1;
}function findMin(arr) { var min = arr[0]; for (var i = 1; i < arr.length; ++i) { if (arr[i] < min) { min = arr[i]; } } return min;
}function findMax(arr) { var max = arr[0]; for (var i = 1; i < arr.length; ++i) { if (arr[i] > max) { max = arr[i]; } } return max;
}function swap(arr, index, index1) { temp = arr[index]; arr[index] = arr[index1];arr[index1] = temp;
}function seqSearch1(arr, data) { for (var i = 0; i < arr.length; ++i) { if (arr[i] == data && i > (arr.length * 0.2)) { swap(arr, i, 0); return true; } else if (arr[i] == data) {return true;}} return false;
}function insertionsort(arr) { var temp, inner; for (var outer = 1; outer <= arr.length-1; ++outer) { temp = arr[outer];inner = outer; while (inner > 0 && (arr[inner-1] >= temp)) { arr[inner] = arr[inner-1]; --inner; } arr[inner] = temp; }
} function binSearch(arr, data) { var upperBound = arr.length-1; var lowerBound = 0; while (lowerBound <= upperBound) { var mid = Math.floor((upperBound + lowerBound) / 2); if (arr[mid] < data) { lowerBound = mid + 1; } else if (arr[mid] > data) { upperBound = mid - 1; } else { return mid; } } return -1;
} function count(arr, data) { var count = 0; var position = binSearch(arr, data); if (position > -1) { ++count; for (var i = position-1; i > 0; --i) { if (arr[i] == data) { ++count; } else { break; } } for (var i = position+1; i < arr.length; ++i) { if (arr[i] == data) { ++count; } else { break; } } } return count;
}function ensureAllStrings(arr) {return arr.map(item => String(item));
}function findSecondSmallest(arr) {if (arr.length < 2) {throw new Error('Array must have at least two elements');}const uniqueElements = Array.from(new Set(arr));if (uniqueElements.length < 2) {throw new Error('Array must have at least two unique elements');}const sortedUniqueElements = ensureAllStrings(uniqueElements).sort((a, b) => a.localeCompare(b));return sortedUniqueElements[1];
}function findKthSmallest(arr, k) {if (k < 1 || k > arr.length) {throw new Error('Invalid k value');}const uniqueElements = Array.from(new Set(arr));if (k > uniqueElements.length) {throw new Error('k is larger than the number of unique elements');}const sortedUniqueElements = ensureAllStrings(uniqueElements).sort((a, b) => a.localeCompare(b));return sortedUniqueElements[k - 1];
}function filterEmptyStrings(arr) {return arr.filter(str => str !== '');
}function generateRandomArray(size, maxVal) { var arr = []; for (var i = 0; i < size; ++i) { arr.push(Math.floor(Math.random() * maxVal)); } return arr;
}function testFindKthSmallest() {var size = 1000;var maxVal = 10000;var arr = generateRandomArray(size, maxVal);console.log("Generated array:", arr);console.log("Second smallest element:", findSecondSmallest(arr));console.log("Third smallest element:", findKthSmallest(arr, 3));console.log("Fourth smallest element:", findKthSmallest(arr, 4));
}testFindKthSmallest();function generateRandomTextArray(size, maxLength) { var arr = []; var characters = 'abcdefghijklmnopqrstuvwxyz'; for (var i = 0; i < size; ++i) { var text = ''; for (var j = 0; j < Math.floor(Math.random() * maxLength); ++j) { text += characters[Math.floor(Math.random() * characters.length)]; } arr.push(text); } return arr;
}function testFindKthSmallestText() {var size = 1000;var maxLength = 10;var arr = generateRandomTextArray(size, maxLength);console.log("Generated text array:", arr);var filteredArr = filterEmptyStrings(arr);console.log("Second smallest element:", findSecondSmallest(filteredArr));console.log("Third smallest element:", findKthSmallest(filteredArr, 3));console.log("Fourth smallest element:", findKthSmallest(filteredArr, 4));
}testFindKthSmallestText();