Find the location of k in an array that starts with an element and increments in a loop?

5, br 8, 9, 10, 10, 3, 3, and 4
given k, find position of k in array,-1
find the position of k in the array with the above characteristics (starting from an element, incrementing in a loop), where k is an arbitrary real number, if found, return the subscript, otherwise return-1, write code to implement

.
Mar.11,2021

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;
}
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-1bf3e83-316fb.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-1bf3e83-316fb.MAI); waiting for someone to free some space... (errno: 28 "No space left on device")
Need Help?