【C语言】数组——二分查找

题1 704.二分查找【简单】

int search(int* nums, int numsSize, int target) {
    
    int left = 0, right = numsSize - 1;
    int mid = (left + right)/2;
    int result = -1;

    while(left<=right){
        
        if(nums[mid] == target){
            result = mid;
            break;
        }else if(nums[mid] > target){
            right = mid-1;
        }else if(nums[mid] < target){
            left = mid+1;
        }
        mid = (left + right)/2;
    }
    return result;
}

题2 35. 搜索插入位置【简单】

int searchInsert(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize-1;
    int mid = (left + right) / 2;
    int result;
    if(target < nums[0])    return result = 0;
    if(target > nums[numsSize-1])    return result = numsSize;
    while(left <= right){
        if(nums[mid] == target)
            return result = mid;
        if(nums[mid] > target){
            right = mid - 1;
            result = left;
        }else if(nums[mid] < target){
            left = mid + 1;
            result = left;
        }
        mid = (left + right) / 2;
    }
    return result;
}

题3 34.在排序数组中查找元素的第一个和最后一个位置【中等】

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {

    int *reslut =  (int *)malloc(sizeof(int)*2);
    reslut[0] = -1; reslut[1] = -1;   
    *returnSize = 2;
    int left = 0, right = numsSize - 1;
    if(0 == numsSize){
        return reslut;
    }  
    while(left <= right){
        int mid1 = (left + right) / 2;       
        if(target==nums[mid1]){
            right = mid1 - 1;
        }else if(target > nums[mid1]){
            left = mid1 + 1;
        }else if(target < nums[mid1]){
            right = mid1 - 1;
        }             
    }
    // reslut[0] = mid1;
    if(left < numsSize && nums[left] == target){
        reslut[0] = left;
    }
    left = 0, right = numsSize - 1;
    while(left <= right){
        int mid2 = (left + right) / 2;
        if(target==nums[mid2]){
            left = mid2 + 1;
        }else if(target < nums[mid2]){
            right = mid2 - 1;
        }else if(target > nums[mid2]){
            left = mid2 + 1;
        }     
    }
    if(right >= 0 && nums[right] == target){
        reslut[1] = right;
    }
    // reslut[1] = mid2; 
    return reslut;
}

题4 69. x 的平方根【简单】

个人解

int mySqrt(int x) {
    int t = 0;
    long long temp = x;
    long long start = 1, end, result;
    if (0 == x)    return 0;
    while (temp >= 1) {
        temp /= 10;
        t++;
    }
    if (0 == t % 2)  t--;
    if (1 == t) {
        start = 1;
    }
    else {
        for (int i = 0; i < t / 2; i++) {
            start *= 10;
        }
    }
    end = start * 10;

    while (start <= end) {
        result = (end + start) / 2;
        if (result * result <= x && (result + 1) * (result + 1) > x) {
            return result;
        }
        else if (result * result < x) {
            start = result + 1;
        }
        else if (result * result > x) {
            end = result - 1;
        }
    }
    return result;
}

牛顿迭代法

int mySqrt(int x) {
	if (x <= 1) return x; // 如果 x 小于等于 1，直接返回 x
     	long r = x;
    	 while (r * r > x) { // 牛顿迭代法
         	r = (r + x / r) / 2;
    	}
    return (int)r;
}

题5 367.有效的完全平方数【简单】

bool isPerfectSquare(int num) {
    //10*10=100，99*99=9801，两位数相乘的位数在 3-4 位,n位在2n
    //初步判断位数
    int t = num,  ii = 0;
    for(int i = 1; t != 0; i++){
        t = t / 10; ii = i;
    } 
    int left, right;
    if(ii%2==1){
        left = pow(10, (ii-1)/2);
        right = pow(10, (ii-1)/2+1);
    }else{
        left = pow(10, ii/2-1);
        right = pow(10, ii/2);
    }
    
    long int mid = (left + right) / 2;
    while(left <= right){
        if(mid*mid < num) left = mid+1;
        if(mid*mid > num) right = mid-1;
        if(mid*mid == num) return true;
        mid = (left + right) / 2;
    }
    return false;
}