Java Binary Search


  • 0
    V

    Worst case is O(n). Average is O(log n).
    To understand low++ and high--, consider below 2 cases-

    • low++ => [3,1,2,2,2],search value=1,rotation shift is 1
    • high-- => [4,4,10,2],search value=10,rotation shift is 3
    public class Solution {
        public boolean search(int[] nums, int target) {       
            int low = 0,
                high = nums.length-1,
                mid = 0;
    
            while(low <= high){
                mid = low + (high-low)/2;
                if(nums[mid] == target) return true;
    
                if(nums[mid] > target){
                    if(nums[low] > target) low++;
                    else high = mid-1;
                }
                else if(nums[mid] < target){
                    if(nums[high] < target) high--;
                    else low = mid+1;
                }
                
            }
            
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.