CODEWITHSUNDEEP
algorithmbinary-search
Maggi Iggam
Maggi Iggam

Reputation: 692

Find place for number in array using binary search

I have an array of numbers , say nums[n] . I have to find position 'i' such that nums[i] is greatest among all integers which are less than key . nums is sorted . I know i can do this using linear search from i=0 till position where nums[i]>=key . But i want to do it faster , so could anyone tell algo of required binary search ?

Example : nums[]={2,4,14,25} and key=15 . Therefore i should be 2 as 14 is greatest integer among all other integers less than 15 .

Upvotes: 2

Views: 4874

Answers (2)

Ethan
Ethan

Reputation: 481

Wayne's method is correct, I made some modifications of the code. My code is in Java.

when a <= nums[mid], all numbers bigger than or equals to key are dropped and high is assigned to mid-1. So when the loop ends, high is the first number less than key or -1. -1 means no number in the given array is less than key.

public static int lessThan(int[] nums, int key){
    if(nums == null || nums.length == 0) return -1;
    int low = 0, high = nums.length -1;
    while(low <= high){
        int mid = (low + high) >> 1;
        if(key <= nums[mid]){
            high = mid - 1;
        }else {
            low = mid +1;
        }
    }
    return high;
}

Upvotes: 3

Wayne Rooney
Wayne Rooney

Reputation: 1607

Remember that in a normal binary search code , the low and high variable used denotes the indices of the array , so you easily know the position .

First look out if a[0]>=key,because there should be atleast 1 element less than key for searching it out.

Then proceed with binary search : Take out the middle element , if this element is >=key then discard all elements to the right of it including it.

However if a[mid] <key ,then discard all elements to the left of it (including it) and take out the max of the element found uptil now or this element.

Code :

    if(a[0]>=key)
    print("Some error message");
    int found=-1;
    int low=0,high=n-1;
    while(low<high)
    {
    int mid=(low+high)/2;
    if(a[mid]>=key)
       high=mid-1;
    else
    {
       low=mid+1;
       found=max(found,a[mid]);
    }

  }

Now you know that after this loop , low will be equal to high so print(low) or print(high)

Upvotes: 3

Related Questions