package com.fishercoder.solutions;

/**
 * 704. Binary Search
 *
 * Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums.
 * If target exists, then return its index, otherwise return -1.
 *
 * Example 1:
 *
 * Input: nums = [-1,0,3,5,9,12], target = 9
 * Output: 4
 * Explanation: 9 exists in nums and its index is 4
 *
 * Example 2:
 *
 * Input: nums = [-1,0,3,5,9,12], target = 2
 * Output: -1
 * Explanation: 2 does not exist in nums so return -1
 *
 * Note:
 *
 * You may assume that all elements in nums are unique.
 * n will be in the range [1, 10000].
 * The value of each element in nums will be in the range [-9999, 9999].
 */
public class _704 {
  public static class Solution1 {
    public int search(int[] nums, int target) {
      int left = 0;
      int right = nums.length - 1;
      if (target < nums[left] || target > nums[right]) {
        return -1;
      }
      if (nums[left] == target) {
        return left;
      } else if (nums[right] == target) {
        return right;
      }
      while (left <= right) {
        int mid = left + (right - left) / 2;
        if (target == nums[mid]) {
          return mid;
        } else if (target > nums[mid]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      return -1;
    }
  }
}

@@ -33,686 +33,8 @@
 s;%0A%0A
-/**%0A * 704. Binary Search%0A *%0A * Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums.%0A * If target exists, then return its index, otherwise return -1.%0A *%0A * Example 1:%0A *%0A * Input: nums = %5B-1,0,3,5,9,12%5D, target = 9%0A * Output: 4%0A * Explanation: 9 exists in nums and its index is 4%0A *%0A * Example 2:%0A *%0A * Input: nums = %5B-1,0,3,5,9,12%5D, target = 2%0A * Output: -1%0A * Explanation: 2 does not exist in nums so return -1%0A *%0A * Note:%0A *%0A * You may assume that all elements in nums are unique.%0A * n will be in the range %5B1, 10000%5D.%0A * The value of each element in nums will be in the range %5B-9999, 9999%5D.%0A */%0A
 publ
@@ -49,16 +49,18 @@
  _704 %7B%0A
+  
   public
@@ -85,16 +85,20 @@
 tion1 %7B%0A
+    
     publ
@@ -139,24 +139,30 @@
 et) %7B%0A      
+  
+    
 int left = 0
@@ -163,16 +163,22 @@
 ft = 0;%0A
+      
       in
@@ -206,24 +206,30 @@
  - 1;%0A      
+    
+  
 if (target %3C
@@ -263,24 +263,32 @@
 s%5Bright%5D) %7B%0A
+        
         retu
@@ -296,26 +296,38 @@
 n -1;%0A      
+   
-%7D%0A
+   %7D%0A      
       if (nu
@@ -352,24 +352,32 @@
 ) %7B%0A        
+    
+    
 return left;
@@ -377,16 +377,22 @@
 n left;%0A
+      
       %7D 
@@ -429,24 +429,32 @@
 ) %7B%0A        
+   
+     
 return right
@@ -461,24 +461,36 @@
 ;%0A      
-%7D%0A
+      %7D%0A   
       
+   
 while (l
@@ -501,24 +501,32 @@
 %3C= right) %7B%0A
+        
         int 
@@ -558,32 +558,40 @@
 t) / 2;%0A        
+  
+      
 if (target == nu
@@ -607,24 +607,34 @@
 %7B%0A          
+       
+   
 return mid;%0A
@@ -633,16 +633,24 @@
 rn mid;%0A
+        
         
@@ -692,16 +692,26 @@
         
+  
+        
 left = m
@@ -722,24 +722,32 @@
  1;%0A        
+     
+   
 %7D else %7B%0A   
@@ -743,16 +743,26 @@
  else %7B%0A
+          
         
@@ -792,18 +792,38 @@
     
-%7D%0A
+        %7D%0A     
       
+ 
 %7D%0A
+      
     
@@ -839,16 +839,22 @@
 -1;%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 704