1.
the following array is a continuous array from 1 to n (n > 2). After breaking the exchange order from the middle, the index of 1 in the array is found by dichotomy.
Array:
Array: [nMuthxipl, nmelxo2,., n-1, n, 1, 2, 3, 4, 5,., nMux]example: [7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 2, 3, 4, 5, 6]
my answer:
step1: sorts the array in ascending order first
example: nasty 15 ~ (nd) ~ (9)) arr = [7, 8, 10, 11, 12, 14, 15, 15, 14, 15, 1, 2, 3, 4, 5, 6]
arr.slice(n-x-1,x).concat(arr.slice(0,n-x-1))
step2: dichotomy search
function getLocation(arr, key, startNum, endNum) {
if (arr == null) return -1;
var middleNum = Math.floor((startNum + endNum) / 2);
console.log(":" + middleNum);
if (startNum < endNum) {
if (key == arr[middleNum]) {
return middleNum + 1;
} else if (key < arr[middleNum]) {
return getLocation(arr, key, startNum, middleNum);
} else {
return getLocation(arr, key, middleNum, endNum);
}
} else if (startNum == endNum) {
return startNum;
} else {
return -1;
}
}
console.log(getLocation([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], 10, 1, 15))
the interviewer says no, you can"t spell it first, just look for it by dichotomy. How can dichotomy be used if it is not in an ordered sequence? Do you feel fucked?