this is loop traversal to judge. Or use the indexOf
method of the array.
var arr = [5, 8, 9, 10, 1, 3, 4];
var k = 3;
function getK(k) {
for(var i = 0; i < arr.length; iPP) {
if(k === arr[i]) {
return i
}
}
return -1
}
var kIndex = getK(k);
console.log('kIndex:', kIndex)
< hr >
the following is a way of binary search, which can reduce the complexity.
var Arr = [3, 5, 6, 7, 9, 12, 15];
function binary(find, arr, low, high) {
if (low <= high) {
if (arr[low] == find) {
return low;
}
if (arr[high] == find) {
return high;
}
var mid = Math.ceil((high + low) / 2);
if (arr[mid] == find) {
return mid;
} else if (arr[mid] > find) {
return binary(find, arr, low, mid - 1);
} else {
return binary(find, arr, mid + 1, high);
}
}
return -1;
}
binary(15, Arr, 0, Arr.length - 1);
indexOf
learn about
ordered queue , and directly use dichotomy, which is to cut the queue into semi-recursive search.
if indexOf, is not allowed, this is actually a very interesting question. Many people may not notice that this is a circular incremental array, which means that there is a minimum value in the array and the maximum value on the left! If you can quickly locate the position of this value, the whole sequence will become an ordered array, and it will be faster to use half-and-half search, but if there is no location, there are some problems with half-and-half search.
< hr >
implement
function MyindexOf(k, arr, l, h) {
if(l==h && k!=arr[l]) return -1;
if(arr[l]==k) return l;
if(arr[h]==k) return h;
if(l>h){
let t=h;
h=l;
l=t;
}
let m=Math.ceil((l + h) / 2);
if(arr[m]==k) return m;
if(m==h||m==l) return -1;//a[m]==a[l]a[m]==a[h]
if(arr[l]<arr[h]){ //
if(arr[h]<k) return -1;
if(arr[l]>k) return -1;
if(arr[m]>k) return MyindexOf(k,arr,l+1,m-1);
return MyindexOf(k,arr,m+1,h-1);
}
//arr[l]==arr[h]arr[l]>arr[h]arr[l]>arr[h]
if(k>arr[l]) {
if(k>arr[m]){
if(arr[m]>arr[l]) return MyindexOf(k,arr,m+1,h-1);//
return MyindexOf(k,arr,l+1,m-1);//
}else{//k>arr[m]
if(arr[m]>arr[l]) return MyindexOf(k,arr,l+1,m-1);//
return -1; //arr[m]<arr[l]
}
}else{ //k<arr[l]
if(k>arr[h]){
return -1;//arr[l]arr[h]
}else{//k<arr[h]
if(k>arr[m]){
return MyindexOf(k,arr,m+1h-1);//arr[m]>arr[h]arr[m]<arr[h]
}else{ //k<arr[m]
if(arr[m]>arr[h]){
return MyindexOf(k,arr,m+1,h-1);
}else{
if(arr[m]<arr[h]) return MyindexOf(k,arr,l+1,m-1);
}
}
}
}
return -1;
}