C: two different binary search implementations, one stuck in an infinite loop

Question

Here are two implementations of a “forgetful” binary search, since they do not check for an exact match until they end.

1)

int bsearch1(int A[], int n, int target)
{
    int low = 0, high = n - 1, mid = 0;
    while (low < high)
    {
        mid = (low + high) >> 1;
        if (target > A[mid])
            low = mid + 1;
        else
            high = mid;
    }
    if (low == high)
    {
        if (A[low] == target)
            return low;
    }

    return -1;
}

2)

int bsearch2(int A[], int n, int target)
{
    int low = 0, high = n - 1, mid = 0;
    while (low < high)
    {
        mid = (low + high) >> 1;
        if (target < A[mid])
            high = mid - 1;
        else
            low = mid;
    }
    if (low == high)
    {
        if (A[low] == target)
            return low;
    }

    return -1;
}

NOTES: nis the length of array A, targetis the element to be found.

bsearch1 , bsearch2 , A = [1,3,5,6], target = 5. - while, bsearch2 bsearch1. . bsearch2 ""? , bsearch2 (, )? .

EDIT: A = [1,3,5,6], target = 5:

1.low = 0, high = 3, mid = 1, A [mid] = 3
2.low = 1, high = 3, mid = 2, A [mid] = 5
3.low = 2, high = 3, mid = 2, A [mid] = 5
...
n.low = 2, high = 3, mid = 2, A [mid] = 5

, bsearch2 low == high , while. , low high low == high bsearch1.

Answer 1

, , high == (low+1). , mid = (low + low + 1)/2, (2*low)/2 + 1/2. mid = low + 0. low = mid, , .

, , - . . high , .

bsearch2 bsearch1 , , - . , . bsearch2 :

mid = (low + high + 1) >> 1;

, , ,

mid = low + ((high - low + 1) >> 1);

, bsearch2, bsearch1 . :

#include <stdio.h>

int bsearch2(int A[], int n, int target)
{
    int low = 0, high = n - 1, mid = 0;
    while (low < high)
    {
        mid = low + ((high - low + 1) >> 1);
        if (target < A[mid])
            high = mid - 1;
        else
            low = mid;
    }
    if (low == high)
    {
        if (A[low] == target)
            return low;
    }

    return -1;
}

int main()
{
    // build a sorted array from 1...20
    int A[20];
    for (int i=0; i<sizeof(A)/sizeof(*A); ++i)
        A[i] = i+1;

    for (int i=0; i<=sizeof(A)/sizeof(*A)+1; ++i)
        printf("Search for %d found index %d\n", i, bsearch2(A, sizeof(A)/sizeof(*A), i));

    return 0;
}

Search for 0 found index -1
Search for 1 found index 0
Search for 2 found index 1
Search for 3 found index 2
Search for 4 found index 3
Search for 5 found index 4
Search for 6 found index 5
Search for 7 found index 6
Search for 8 found index 7
Search for 9 found index 8
Search for 10 found index 9
Search for 11 found index 10
Search for 12 found index 11
Search for 13 found index 12
Search for 14 found index 13
Search for 15 found index 14
Search for 16 found index 15
Search for 17 found index 16
Search for 18 found index 17
Search for 19 found index 18
Search for 20 found index 19
Search for 21 found index -1

, .

Answer 2

, - 1, - 3, - 2.

while "" , , (5) A [mid], .

,

while (low<high && A[mid]!=target) {
…
}

.

Answer 3

, , , . , mid, high low.

, mid . :

high = mid - 1 >= 0 ? mid - 1 : 0;

Answer 4

, int. "". "", "". . , if (l == r-1), (==)?:... , , , . high = mid. .

, " " , mid == A [], - high. A [], A [L], - .

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

bool search(vector<int>& nums, int target) {
    //the key of binary search  
    //1. l and r have to always "squeeze" the target. That is how we move r and l, and how we consider to do r = m or r = m-1 (see 378. Kth Smallest Element in a Sorted Matrix )
    //             if(count < k) { l = midv+1;}             else { r = midv;}
    //2. Try to exclude half of the data 
    int l = 0, r = nums.size()-1;
    int m, mval;

    while(l<=r) {
        m = l + ((r-l)>>1), mval = nums[m];
        if (mval == target) return true;
        if( mval < nums[r]) { //first see where the pivot is
           if(mval < target && target <= nums[r]) l = m+1;
           else r = m-1;
        } else if ( mval > nums[r] ) {
            if(nums[l] <= target && target < mval) r = m-1;
            else l = m+1;
        } else {//mval == nums[r], cannot decide pivot 
            --r; //move r while still be confident taht target is still in between
        }
    }
    return false;
}