二分法三种模型

Posted on | In

二分法三种模型

时间复杂度

T(n) = T(n/2) + O(1) = O(logn)

T(n) = T(n/2) + O(n) = O(n)

left <= right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  /**
    * left <= right
    * @param nums
    * @param target
    * @return
    */
public int binarySearch(int[] nums, int target) {
   int left = 0, right = nums.length - 1; // [left,right]
   while (left <= right) { // left == right
      int mid = (right - left) / 2 + left;
      if (nums[mid] < target) {
         left = mid + 1; // [mid + 1,right]
      } else if (nums[mid] > target) {
         right = mid - 1; // [left ,mid - 1]
      } else {
         return mid;
      }
   }
   return -1;
}

left < right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* left < right
*
* @param nums
* @param target
* @return
*/
public int binarySearch2(int[] nums, int target) {
   int left = 0, right = nums.length;// [left,right)
   while (left < right) {// when left == right then end
      int mid = (right - left) / 2 + left;
      if (nums[mid] < target) {
         left = mid + 1; // [mid+1,right)
      } else if (nums[mid] > target) {
         right = mid;// [left,mid)
      } else {
         return mid;
      }
   }
   return -1;
}

left + 1 < right

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* left + 1 < right
* 相邻则跳出条件
* @param nums
* @param target
* @return
*/
public int binarySearch3(int[] nums, int target) {
   int left = 0, right = nums.length - 1;// [left,right]
   while (left + 1 < right) {// when left + 1 == right then end
      int mid = (right - left) / 2 + left;
      if (nums[mid] < target) {
         left = mid; // [mid,right]
      } else if (nums[mid] > target) {
         right = mid;// [left,mid]
      } else {
         return mid;
      }
   }
   if (nums[left] == target)
      return left;
   if (nums[right] == target)
      return right;
   return -1;
}