704. Binary Search

Problem 704

https://leetcode.com/problems/binary-search/ Given a sorted (in ascending order) integer array nums of nelements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1. Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Solution

v1

int search2(int* nums, int numsSize, int target){
    int l=0, r=numsSize, mid = r/2;
    while (l<r){
        mid = (l+r)/2;
        if( target == *(nums+mid) ) return mid;
        else if( target < *(nums+mid) ) r = mid;
        else l = mid+1;
    }
    return -1;
}

v2

int search(int* nums, int numsSize, int target){
    return binery( nums, numsSize, target, 0 );

}
int binery(int* nums, int numsSize, int target, int piv){
    int mid = numsSize / 2;
    
    if ( target == *(nums+mid) ) return piv + mid;
    if (mid <= 0) return -1;
    if ( target < *(nums+mid) ) return binery( nums, mid, target, piv );
    else return binery( nums+mid, numsSize-mid, target, mid+piv);
}