算法總結—二分搜索與旋轉排序數組 -开发者知识库

算法總結—二分搜索與旋轉排序數組 -开发者知识库,第1张

一. 二分搜索(Binary Search)模板及其理解

1.通用模板,解決start, end, mid, <(<=), >(>=)等問題

http://www.lintcode.com/en/problem/binary-search/

class Solution {
public:
    /**
     * @param nums: The integer array.
     * @param target: Target number to find.
     * @return: The first position of target. Position starts from 0. 
     */
    int binarySearch(vector<int> &array, int target) {
        // write your code here
        if(array.size() == 0){
            return -1;
        }
        int start = 0, end = array.size() - 1;
        while(start   1 < end){
            int mid = start   (end - start) / 2;
            if(array[mid] == target){
                end =  mid;
            }else if(array[mid] < target){
                start = mid;
            }
            else{
                end = mid;
            }
        }
        if(array[start] == target){
            return start;
        }
        if(array[end] == target){
            return end;
        }
        return -1;
    }
};

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复