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

.
Javascript
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;
}

Previous: How should I build a mysql table for this requirement?

Next: Failure to open after ubuntu16.4 installation of 32-bit chrome, is complete

css mysql arrays josn react html typescript webpack npm sass R objective-c .net sql-server jquery python-3.x angularjs django angular excel regex iphone ajax linux xml pandas vba spring database wordpress string wpf xcode windows bash postgresql oracle multithreading eclipse list firebase algorithm macos forms image scala visual-studio azure bootstrap spring-boot react-native python-2.7 docker performance function winforms matlab powershell apache dataframe api sqlite numpy rest shell selenium flutter dart maven loops qt swing android-studio csv express file class tensorflow sorting codeigniter perl
© 2021 CodesHelper
Advertising Contact us About us
Menu