chen-w
7/18/2017 - 11:40 PM

## binary search

binary search

``````// binary search template

// 1. search for first position using while loop
// avoid using stack in case of overflow. stack is not big.
// Timing complexity O(nlogn)

// keypoints:
// 1. start + 1 < end  (loop ends when start and end are one step away from each other)
// rate case: if you use start < end (start==1,end==2), and if you don't use mid+1 or mid-1 when updating start/end.
// There will be a infinity loop.
// 2. start + (end - start) / 2 (because start + end may overflow)
// 3. A[mid] ==, <, >
// 4. A[start] A[end] ? target
class Solution {
public int binarySearch(int[] A, int target) {
if (A == null || A.length == 0) { // array could be empty and null
return -1;
}

int start = 0;
int end = A.length - 1;
int mid;

while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
end = mid;
} else if (A[mid] < target) {
start = mid;
} else if (A[mid] > target) {
end = mid;
}
}

if (A[start] == target) {
return start;
}
if (A[end] == target) {
return end;
}

return -1;
}
}

// 2. serach for first position using recursion
// show people I can also use recursion
class Solution {
public int binarySearch(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}

int start = 0;
int end = A.length - 1;
int mid;

while (start + 1 < end) {
mid = start + (end - start) / 2;
if (A[mid] == target) {
end = start; // difference
} else if (A[mid] < target) {
start = mid;
} else if (A[mid] > target) {
end = mid;
}
}

// difference
if (A[end] == target) {
return end;
}
if (A[start] == target) {
return start;
}

return -1;
}
}

// recursive
class Solution {
public int binarySearch(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}

}
public int binarySearchFunc
}

``````