p23 二分搜索 (leetcode 704)

一:解题思路

这道题目是一道原始的二分搜索问题,比较简答。在写代码的时候,需要注意几个细节问题就行。

二:完整代码示例 (C++版和Java版)

C++:

class Solution 
 {
 public:
     int search(vector<int>& nums, int target) 
     {
         int ret = -1;
         int begin = 0;
         int end = nums.size() - 1;

         while (begin <= end)//需要注意这里是<=
         {
             int mid = begin + (end - begin) / 2;//如果想进一步的提升效率的话,可以将/改为>>

             if (nums[mid] > target)
             {
                 end = mid - 1;
             }
             else if (nums[mid] < target)
             {
                 begin = mid + 1;
             }
             else
             {
                 ret = mid;
                 break;
             }
         }

         return ret;
     }
 };

Java:

class Solution
{
    public int search(int[] nums, int target)
    {
          int ret=-1;
          int begin=0,end=nums.length-1;
          
          while(begin<=end)
          {
              int mid=begin+((end-begin)>>1);
              
              if(nums[mid]>target)
              {
                  end=mid-1;
              }
              else if(nums[mid]<target)
              {
                  begin=mid+1;
              }
              else
              {
                  ret=mid;
                  break;
              }
          }
          
          return ret;
    }
}

 

上一篇:704. Binary Search


下一篇:leetcode 704.二分查找