samedi 5 août 2023

Can we use condition front != end in binary search?

I know that we use while(front <= end) in binary search. I was thinking the can we use the condition while(front != end) like in the code here? I cannot find a case where it might fail.

class BinarySearch {
public:
    int bin_search(vector<int>& nums, int target) {
        int count = nums.size();
        int front = 0;
        int end = count - 1;

        if(nums[0]==target){return 0;}
        while(front!=end){

            int mid = (end + front)/2;
            // cout<<mid<<endl;
            if(nums[front] == target){return front;}
            else if(nums[end] == target){return end;}


            else if(nums[mid]==target){return mid;}

            else if(nums[mid]<target){
                front = mid+1;
            }

            else if(nums[mid]>target){
                end = mid - 1;
            }
        }

        return -1;
    }
};

Since I am checking the condition for nums[front] and nums[end] in every while loop, I don't think this code should fail. I tried it on bunch of test cases and I am getting correct answers but I am asking in case I missed any corner case where it could fail.

Aucun commentaire:

Enregistrer un commentaire