Ad

Why Is My Binary Search Stuck In An Endless Loop?

- 1 answer

I just had to pop in here to hopefully get a quick answer to my little problem. I'm trying to create a binary search method but ran into some problems. I created it iteratively, which my IDE(Intellij) apparently didn't like. It had me stuck in a endless loop of... well, you know the rest. Any suggestions?

Here is my simple, yet beautiful little snippet of code:

static int searchIt(int[] arr, int target){    
    int left = 0;                              
    int right = arr.length - 1;                
    while (left <= right){                     
        int mid = (right + left) / 2;          
        if(arr[mid] == target) {               
            return mid;                        
        } else if(target < arr[mid]){          
            right = mid-1;                     
        } else{                                
            left = mid -1;                     
        }                                      
    }                                          
    return -1;                                 
}                                              

No errors, not in runtime or compile time, just endless nothingness...

Ad

Answer

left value should be mid + 1 since if the your middle your target value greater than your mid value then you need to search the element in second half of your array

static int searchIt(int[] arr, int target){    
    int left = 0;                              
    int right = arr.length - 1;                
    while (left <= right){                     
        int mid = (right + left) / 2;          
        if(arr[mid] == target) {               
            return mid;                        
        } else if(target < arr[mid]){          
            right = mid - 1;                     
        } else{                                
            left = mid + 1;                     
        }                                      
    }                                          
    return -1;                                 
} 
Ad
source: stackoverflow.com
Ad