leetcode二分查找问题整理-白红宇

自从做完leetcode上的三道关于二分查找的题后，我觉得它是比链表找环还恶心的题，首先能写出bugfree代码的人就不多，而且可以有各种变形，适合面试的时候不断挑战面试者，一个程序猿写代码解决问题的能力都能在这个过程中考察出来。

在有序数组中寻找等于target的数的下标，没有的情况返回应该插入的下标位置：

public int searchInsert(int[] A, int target) {        // Note: The Solution object is instantiated only once and is reused by each test case.        int start = 0;        int end = A.length-1;               while(start<=end){                            //  小于等于            int mid = start + (end-start)/2;            if(A[mid]
     
      target)                end = mid-1;                            //  mid减1            else                return mid;        }               return start;    }

在不重复的旋转数组中寻找等于target的数的下标，没有的话返回-1 ：

class Solution {public:    int search(int A[], int n, int target) {        if(n<=0)            return -1;        int mid;        int start=0;        int end=n-1;        while(start<=end)        {            mid=(start+end)/2;            if(A[mid]==target)                return mid;            else if(A[mid]>=A[start])            {                if(target>=A[start]&&target
     
      A[mid]&&target<=A[end])                    start=mid+1;                else                    end=mid-1;            }        }        return -1;    }};

在有重复的旋转数组中判断是否存在等于target的数：

class Solution {public:    bool search(int A[], int n, int target) {        if(n==0)            return false;        int mid;        int start=0;        int end=n-1;        while(start<=end)        {            mid=(start+end)/2;            if(A[mid]==target)                return true;            else if(A[mid]>A[start])            {                if(target
     
      =A[start])                    end=mid-1;                else                    start=mid+1;            }            else if(A[mid]
      
       A[mid]&&target<=A[end])                    start=mid+1;                else                    end=mid-1;            }            else                 start++;        }        return false;    }};

旋转数组中查找最小值，当没有重复元素时：

class Solution {public:    int findMin(vector
     
       &num)    {        if(num.empty())            return 0;        int s=0;        int t=num.size()-1;        int mid;        while(s

在有重复元素的时候，查找旋转数组中的最小值：

class Solution {public:    int findMin(vector
     
       &num)    {        if(num.empty())            return 0;        int s=0;        int t=num.size()-1;        while(s
      
       =num[s])                s=mid+1;            else                t=mid;        }        return num[s];    }};