33. 搜索旋转排序数组

搜索旋转排序数组

一、思想

时间复杂度为O(n),使用遍历。时间复杂度为O(logn),使用二分查找。

二、代码实现

1、遍历

var search = function(nums, target) {
    const n = nums.length;
    
    for(let i=0;i<n;i++){
        if(nums[i] == target){
            return i;
        }
    }
    return -1;
};

2、二分查找

对于有序数组，可以使用二分查找的方法查找元素。
利用二分查找实现的思想
在这里插入图片描述

var search = function(nums, target) {
    // 随便选择一个点mid，将数组分为两部分，一定有一部分是有序的。
    var start = 0, end = nums.length-1;
    
    while(start <= end){
    	// 为什么不写成 const mid = (start+end)//2 ,因为考虑到left+right的溢出边界情况
    	const mid = start + ((end - start) >> 1)；
    	      
        // 判断nums[mid]是否是target
        if(target == nums[mid]) return mid;
              
        // 确定有序的部分，如果[start,mid]部分有序
        if(nums[mid] >= nums[start]){
            
            // 确定target的位置,从而移动指针的位置，改变mid
            if(target >= nums[0] && target < nums[mid]){
                end = mid-1;
            }else{
                start = mid+1;
            }     
        }
        
        
        // 如果[mid,end]部分有序
        if(nums[mid] <= nums[end]){
            if(target > nums[mid] && target <= nums[end]){
                start = mid+1;
            }else{
                end = mid-1;
            }
        }
    }
    return -1;
};