An algorithm problem of dichotomy

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?

Mar.05,2021

isn't the first one in the ordinal array 1? why are you still two points? Moreover, there is sorting time, complexity o (nlogn), you scan the array has not been scanned out? So where are the points that are sorted first and then dichotomized?

No, there is a strange thing in your answer! You all know that the cutting position is 9, but also from the position of 9 slice open, and then exchange positions concat and then binary search? What? What the heck, if you all know to cut the array from 9, the answer is 9: 1!

so let's examine the question first.

    The
  1. array is an ordered array of 1 to n that is broken and spliced in the middle, so the two parts of the array itself are ordered
  2. .
  3. is looking for the location of 1. To put it bluntly, it is to find the location where the array is broken and then spliced

solution: if I < j < k, then arr [I] ide of the inequality is not true, it means that which side is not continuously ascending, and the splicing point is at which end.


do you want to find it after sorting? Isn't it directly in the first one? So what's the point of your answer!

MySQL Query : SELECT * FROM `codeshelper`.`v9_news` WHERE status=99 AND catid='6' ORDER BY rand() LIMIT 5
MySQL Error : Disk full (/tmp/#sql-temptable-64f5-7ac97a-1c602.MAI); waiting for someone to free some space... (errno: 28 "No space left on device")
MySQL Errno : 1021
Message : Disk full (/tmp/#sql-temptable-64f5-7ac97a-1c602.MAI); waiting for someone to free some space... (errno: 28 "No space left on device")
Need Help?