I've array of N integers in not-decreasing order. Need to find any specific element in array, if found then return the position of that array otherwise returns -1

public static int find(int[] v, int bb) {
    int N = v.length;
    if (N == 0) {
        return -1;
    }
    int l = 0;
    int r = N - 1;
    while (l < r) {
        int m = (l   r) / 2;
        if (v[m] > bb) {
            r = m - 1;
        } else {
            l = m;
        }
    }
    if (v[l] == bb) {
        return l;
    }
    return -1;
}

there's one bug I need to find out, which is about that this will not work for some inputs. I gave up.

Any suggestions ?

CodePudding user response：

There are several errors within your code. First of all, you need the equal case within your loop not outside, or else you'll keep shifting your range completely missing the value to be found.

Secondly, as you're shifting the range from the "right" side with r = m - 1;, you need to do the same thing with the "left" side or you might loop indefinitely.

This is the fixed version of your code:

public static int find(int[] v, int bb) {
    if (v.length == 0) {
        return -1;
    }

    int l = 0;
    int r = v.length;
    int m;

    while (l < r) {
        m = (l   r) / 2;
        if (v[l] == bb) {
            return l;
        } else if (v[m] > bb) {
            r = m - 1;
        } else {
            l = m   1;
        }
    }

    return -1;
}

On a side note, you might want to place that m declaration outside the loop. It's not really that efficient nor a best practice re-daclaring a variable at every iteration of a loop.

CodePudding user response：

First of all, I think you should name your variables with a proper name, and not just with a single characters, it'll make your code easier to understand.

Second, you are using a binary serach algorithm, if you want that code to work correctly you have to use an increasing ordered array. Here you have a binary search method that should work with increasing ordered arrays:

public static int binarySeacrh(int [] list, int numSearched) {
    
    boolean found = false;
    int start = 0;
    int end = list.length - 1;
    int pos = -1;

    while(start <= end && !found){
        int middle=((start   end) / 2);
        if (numSearched == list[middle]){
            found = true;
            pos = middle;
        } 
        else if (list[middle] < numSearched){
            start = middle   1;
        }else{
            end = middle - 1;
        }
    }
    
    return pos;
}

If you want to search for the position in a unordered array, you must use another type of serach algorithm or order the array first.

CodePudding user response：

If you want to locate the index of the first specific numerical element within the array then you can do something like this:

public static int find(int[] v, int bb) {
    int found = -1;
    for (int i = 0; i < v.length; i  ) {
        if (v[i] == bb) {
            found = i;
            break;
        }
    }
    return found;
}  

If there are multiple values in the array that are the same as bb then the method above will only provide the first one found. If you want to return the index values for all values of bb found in the array then you would want to return an array of index values, for example:

public static int[] find(int[] v, int bb) {
    List<Integer> list = new ArrayList<>();
    int found = -1;
    for (int i = 0; i < v.length; i  ) {
        if (v[i] == bb) {
            found = i;
            list.add(found);
        }
    }
    if (found == -1) { 
        list.add(found); 
    }
    return list.stream().mapToInt(d -> d).toArray();
} 

The List Interface is used in the above example because it can grow dynamically since we have no idea how many values of bb are actually going to be contained within the Array. The List is converted to an int[] array before it is returned.